axyz

Se consideră numerele naturale $A$ (format din două sau trei cifre, toate distincte și nenule) și $X$ (format din $N$ cifre, toate nenule).

Din numărul $X$, folosind toate cele $N$ cifre ale sale, se poate construi un cel mai mare număr natural $Y$ strict mai mic decât $\textbf{X}$. De exemplu, pentru $X=121621$ se construiește $Y=121612$.

Tot din numărul $X$, se poate obține numărul $A$ prin ștergerea unor cifre din scrierea lui $X$ și alipirea celor rămase, fără a le schimba ordinea. De exemplu, dacă $X=121621$ și $A=12$, există $Z=3$ posibilități distincte prin care să obținem numărul $A$ din $X$ și anume: 1) $\textbf{\textcolor{red}{12}} \sout{1621}$; 2) $\textbf{\textcolor{red}1} \sout{216} \textbf{\textcolor{red}2} \sout{1}$; 3) $\sout{12} \textbf{\textcolor{red}1} \sout{6} \textbf{\textcolor{red}2} \sout{1}$.

Cerință

Cunoscându-se numerele $A, N$ și cele $N$ cifre ale lui $X$, să se determine:

1. cel mai mare număr natural $Y$, strict mai mic decât $\textbf{X}$, care se poate obține rearanjând cifrele lui $X$;
2. numărul maxim $Z$ de posibilități distincte prin care se poate obține numărul $A$ din numărul $X$ prin ștergerea unor cifre și alipirea celor rămase, fără a le schimba ordinea.

Date de intrare

Fişierul de intrare axyz.in conține:

• pe prima linie un număr natural $p$; pentru toate testele de intrare, numărul $p$ poate avea doar valoarea $1$ sau valoarea $2$;
• pe a doua linie, numărul $A$, cu semnificația din enunț;
• pe a treia linie numărul de cifre ale numărului $X$;
• pe a patra linie, un șir de $N$ cifre, separate prin câte un spațiu, reprezentând cifrele numărului $X$, în această ordine.

Date de ieșire

• Dacă valoarea lui $p$ este $1$, atunci se va rezolva numai cerința $\textbf{1}$. În acest caz, fişierul de ieşire axyz.out va conţine pe prima linie un șir de cifre reprezentând numărul natural $Y$ determinat (răspunsul la cerința $1$).
• Dacă valoarea lui $p$ este $2$, atunci se va rezolva numai cerința $\textbf{2}$. În acest caz, fişierul de ieşire axyz.out va conține pe prima linie un număr natural reprezentând numărul $Z$ determinat (răspunsul la cerința $2$).

Restricții și precizări

• $12 \leq A \leq 987$;
• $10 \leq N \leq 30 \ 000$;
• Pentru toate datele de test, numerele $\textbf{Y}$ și $\textbf{A}$ pot fi obținute din numărul $\textbf{X}$.
• Pentru rezolvarea corectă a cerinţei $1$ se acordă $30\%$ din punctaj, iar pentru rezolvarea corectă a cerinţei $2$ se acordă $70\%$ din punctaj.

Exemplul 1

axyz.in

1
12
6
1 2 1 6 2 1

axyz.out

121612

Explicație

Se rezolvă cerința $1$. $A=12$, $N=6$, $X=121621$.

Cel mai mare număr $Y$ strict mai mic ca $X$ este: $Y=121612$

Exemplul 2

axyz.in

2
12
6
1 2 1 6 2 1

axyz.out

3

Explicație

Se rezolvă cerința $2$. $A=12$, $N=6$, $X=121621$.
Sunt $Z=3$ posibilități distincte prin care se obține numărul $A$ din $X$:

1. $\textbf{\textcolor{red}{12}} \sout{1621}$;
2. $\textbf{\textcolor{red}1} \sout{216} \textbf{\textcolor{red}2} \sout{1}$;
3. $\sout{12} \textbf{\textcolor{red}1} \sout{6} \textbf{\textcolor{red}2} \sout{1}$.