== include(page="template/taskheader" task_id="anagrame") ==

Se dau două şiruri S{~1~} si S{~2~} formate doar cu litere mici. Numim subşir de lungime K al unui şir a un şir a’=  a{~i{~1~}~},  a{~i{~2~}~},...,  a{~i{~K~}~}, astfel încât să avem: i{~1~} <  i{~2~} <  ...  <  i{~K~}.

Se dau două şiruri $S{~1~}$ si $S{~2~}$ formate doar cu litere mici. Numim subşir de lungime $K$ al unui şir a un şir $a’=  a{~i{~1~}~},  a{~i{~2~}~},...,  a{~i{~K~}~}$, astfel încât să avem: $i{~1~} <  i{~2~} <  ...  <  i{~K~}$.

Să se determine lungimea maximă a unui subşir din S{~1~}, format prin concatenarea unor anagrame ale şirului S{~2~}. Dintre toate subşirurile cu lungime maximă se va determina cel care este cel mai mic lexicografic. Un şir de lungime *na* se consideră mai mic lexicografic decât un şir de lungime *nb* dacă există un indice i, astfel încât a{~1~}=b{~1~}, a{~2~}=b{~2~},..., a{~i-1~}=b{~i-1~} şi a{~i~}<b{~i~}. Un şir a este anagrama unui şir b dacă sortându-le crescător pe fiecare se obţin două şiruri identice.

Să se determine lungimea maximă a unui subşir din $S{~1~}$, format prin concatenarea unor anagrame ale şirului $S{~2~}$. Dintre toate subşirurile cu lungime maximă se va determina cel care este cel mai mic lexicografic. Un şir de lungime $n{~a~}$ se consideră mai mic lexicografic decât un şir de lungime $n{~b~}$ dacă există un indice {$1 &le; i &le; min(n{~a~}, n{~b~})$}, astfel încât $a{~1~}=b{~1~}, a{~2~}=b{~2~},..., a{~i-1~}=b{~i-1~}$ şi $a{~i~}<b{~i~}$. Un şir $a$ este anagrama unui şir $b$ dacă sortându-le crescător pe fiecare se obţin două şiruri identice.

h2. Date de intrare

În fişierul anagrame.in, pe prima linie se află un număr natural P. Pe linia a doua se află şirul S{~1~}, iar pe a treia linie se află şirul S{~2~}.

În fişierul anagrame.in, pe prima linie se află un număr natural $P$. Pe linia a doua se află şirul $S{~1~}$, iar pe a treia linie se află şirul $S{~2~}$.

h2. Date de ieşire

În fişierul $anagrame.out$, dacă P=1, atunci pe prima linie se va scrie un număr natural reprezentând lungimea maximă a unui şir cu proprietatea cerută, iar dacă P=2, atunci pe prima linie se va scrie subşirul de lungime maximă cu proprietatea cerută şi minim lexicografic.

În fişierul $anagrame.out$, dacă $P=1$, atunci pe prima linie se va scrie un număr natural reprezentând lungimea maximă a unui şir cu proprietatea cerută ({*exprimat in numarul de anagrame - vezi exemplul*}), iar dacă $P=2$, atunci pe prima linie se va scrie subşirul de lungime maximă cu proprietatea cerută şi minim lexicografic.

h2. Restricţii

* $1 ≤ Lungime(S{~2~}) ≤ Lungime(S{~1~}) ≤ 100000$
* Se garantează că cel puţin o anagramă a lui S{~2~} apare în S{~1~}

* $1 ≤ Lungime(S{~2~}) ≤ Lungime(S{~1~}) ≤ 10^5^$
* Se garantează că cel puţin o anagramă a lui $S{~2~}$ apare în $S{~1~}$

h2. Exemplu

table(example). |_. anagrame.in |_. anagrame.out |_. explicatie |

table(example). |_. anagrame.in |_. anagrame.out |_. Explicatie |

| 1
  abbaaabababbaabaabba
  aba

| 15
| Deoarece a apare de 11 ori, S2 poate să apară de cel mult 5 ori.

| 5
| Deoarece a apare de $11$ ori, $S2$ poate să apară de cel mult $5$ ori.

  Se observă subşirul format cu litere îngroşate şi

  subliniate {*+ab+*}ba{*+aababa+*}b{*+baabaa+*}bba deci *abaaabababaabaa* este un subşir
  de lungime maximă, egală cu 15, cu proprietatea cerută.

  subliniate ${*+ab+*}ba{*+aababa+*}b{*+baabaa+*}bba$ deci *$abaaabababaabaa$* este un subşir
  de lungime maximă, egală cu $15$, cu proprietatea cerută. _Afisam *$5$* deoarece am concatenat *$5$* anagrame_

|
| 2
  abbaaabababbaabaabba