anagrame

Se dau două şiruri $S1$ si $S2$ formate doar cu litere mici. Numim subşir de lungime $K$ al unui şir $a$ un şir $a^\prime = a_{i_1} + a_{i_2} + \dots + a_{i_K}$, astfel încât să avem $i_1 \lt i_2 \lt \dots \lt i_K$.

Cerință

Să se determine lungimea maximă a unui subşir din $S1$, format prin concatenarea unor anagrame ale şirului $S2$. Dintre toate subşirurile cu lungime maximă se va determina cel care este cel mai mic lexicografic.

Un şir $a$ de lungime $n$ se consideră mai mic lexicografic decât un şir $b$ de lungime $n$ dacă există un indice $i$ astfel încât $a_1=b_1$, $a_2=b_2$, $\dots$, $a_{i-1}=b_{i-1}$ şi $a_i \lt b_i$. Dacă lungimile celor două șiruri diferă, șirul cu lungimea mai mică se consideră minim lexicografic.

Un şir $a$ este anagrama unui şir $b$ dacă, sortându-le crescător pe fiecare, se obţin două şiruri identice.

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 $S1$, iar pe a treia linie se află şirul $S2$.

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.

Restricții și precizări

• $1 \leq |S2| \leq |S1| \leq 10^5$, unde $|a|$ este lungimea șirului $a$.
• Se garantează că cel puţin o anagramă a lui $S2$ apare în $S1$.

Exemplul 1

anagrame.in

1
abbaaabababbaabaabba
aba

anagrame.out

15

Explicație

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

Se observă subşirul format cu litere subliniate $\text{\underline{ab}b\underline{aaababa}b\underline{baabaa}bba}$ deci $\text{abaaabababaabaa}$ este un subşir de lungime maximă, egală cu $15$, cu proprietatea cerută.

Exemplul 2

anagrame.in

2
abbaaabababbaabaabba
aba

anagrame.out

abaaabaabaabaab

Explicație

Se observă că subşirul verifică proprietatea cerută.