decod

Numim $k$ - $p$ - platou un număr $n$ de forma $c_1 c_2 \dots c_p$ cu proprietatea că cifrele sale sunt distincte şi aparţin mulţimii $\{k$, $k+1$, $\dots$, $k+p-1\}$. O $\alpha$-codificare constă în transformarea numărului $n$ în numărul $d_1 d_2 \dots d_p$, unde $d_i$ = $1$ + numărul de cifre din stânga cifrei $c_i$ care sunt mai mici decât $c_i$ pentru $1 \leq i \leq p$. Aplicând o $\alpha$-codificare unui număr obţinem un $\alpha$-cod.

Fie $s$ un şir format din secvenţe de cifre, în care fiecare secvenţă are aceeaşi lungime $p$. Un val este o succesiune de astfel de secvenţe în care orice secvenţă care este un $\alpha$-cod, este urmată de o secvenţă care nu este un $\alpha$-cod şi orice secvenţă care nu este un $\alpha$-cod, este urmată de o secvenţă care este un $\alpha$-cod, cu excepţia ultimei secvenţe. Un val începe obligatoriu cu o secvenţă ce reprezintă un $\alpha$-cod şi se termină cu o secvenţă care nu este un $\alpha$-cod.

Primul caracter al unui val se poate afla pe o poziţie din $s$ care aparţine mulţimii $\{1$, $1+p$, $1+2p$, $1+3p$, $\dots\}$.

Cerinţe

Scrieţi un program care:

1. cunoscând numerele $k$, $p$ şi un $\alpha$-cod, determină $k$ - $p$-platoul căruia i s-a aplicat $\alpha$-codificarea.
2. pentru un şir de cifre $s$ dat, determină lungimea celui mai lung val.

Date de intrare

Fişierul de intrare decod.in conţine:

• pe prima linie cifrele $k$ şi $p$ separate printr-un spaţiu
• pe a doua linie un $\alpha$-cod a unui $k$ - $p$ - platou
• pe a treia linie un şir de cifre $s$

Date de ieşire

Fişierul de ieşire decod.out va conţine:

• pe prima linie $k$ - $p$ - platoul căruia i s-a aplicat $\alpha$-codificarea
• pe a doua linie lungimea celui mai lung val

Restricții și precizări

• $1 \leq k \leq 9$
• $1 \leq p \leq 9$
• $k + p - 1 \leq 9$
• $1 \leq d_i \leq 9$
• şirul $s$ are cel mult $800 \ 000$ de caractere
• Pentru rezolvarea cerinţei $1$ se acordă $40\%$ din punctaj şi pentru cerinţele $1$ şi $2 \ 100\%$ din punctaj.

Exemplul 1

decod.in

3 5
12124
1111012124100111234511151

decod.out

57346
20

Explicație

Numărul $57346$ este un $3$ - $5$ - platou, deoarece cifrele sale aparţin mulţimii {$3$, $4$, $5$, $6$, $7$}. Aplicându-i o $\alpha$ - codificare se obţine $12 \ 124$, $1$ deoarece în stânga lui $5$ nu există nici o cifră mai mică decât $5$ ($1 + 0$), $2$ deoarece în stânga lui $7$ există o cifră mai mică decât $7$ ($1 + 1$) etc.

În şirul 1111012124100111234511151 avem un val de lungime $20$.

Exemplul 2

decod.in

8 2
12
10121011101012101110111011101110

decod.out

89
20

Explicație

Numărul $12$ este un $\alpha$-cod a numărului $89$.
În şirul 10121011101011101110111011201110 avem două valuri, iar valul maxim are lungimea egală cu $20$.