Să se calculeze cel mai lung subşir de cuvinte din şirul iniţial ce respectă următoarele proprietăţi :

* Pentru orice $i$ , $1 ≤ i ≤ M-1$ , ultimul caracter al lui $C{~i~}$ este egal cu primul caracter al lui $C{~i+1~}$
* Pentru orice $i$ , $1 ≤ i ≤ M-1$ , $P{~i+1~} - P{~i~} ≤ K$ , pentru un $K$ dat

* Pentru orice $i$ , $1 ≤ i ≤ M-1$ , ultimul caracter al lui $C ~i~$ este egal cu primul caracter al lui $C ~i+1~$
* Pentru orice $i$ , $1 ≤ i ≤ M-1$ , $P ~i+1~ - P ~i~ ≤ K$ , pentru un $K$ dat

Unde $M$ este lungimea noului şir rezultat , $C{~i~}$ este cuvântul aflat pe poziţia $i$ în noul şir şi $P{~i~}$ este poziţia pe care se află cuvântul $C{~i~}$ în şirul iniţial.

Unde $M$ este lungimea noului şir rezultat , $C ~i~$ este cuvântul aflat pe poziţia $i$ în noul şir şi $P ~i~$ este poziţia pe care se află cuvântul $C ~i~$ în şirul iniţial.

h2. Date de intrare

h2. Restricţii

* $1 ≤ N ≤ 500 000$

* $1 ≤ N ≤ 100 000$

* $1 ≤ K ≤ N$
* $2 ≤ lungimea oricărui cuvânt ≤ 10$

10158