prefixe

Prefixe

După cum ştiţi, lui Gigel îi plac cifrele $0$ şi $1$. În această problemă, îi place şi cifra $2$. El analizează un şir de caractere $T$ format doar din $0$, $1$ şi $2$ şi este fascinat de şabloanele pe care le observă în şir. Caracterul $T{~1~}$ este primul caracter al şirului, $T{~2~}$ al doilea, etc. Şirul are lungime $N$.

Gigel este interesat de prefixele $T{~1~}, ..., T{~i~}$ ale acestui şir ({$1 ≤ i ≤ n$}). El observă că un astfel de prefix de lungime $i$ are la rândul lui anume prefixe care îi sunt şi sufixe. De exemplu, dacă $T = 0101012$ şi $i = 5$, în prefixul $01010$ se găseşte prefixul $010$ care este şi sufix. Vă roagă să gasiţi pentru fiecare prefix $T{~1~}, ..., T{~i~}$ lungimea celui mai mare prefix diferit de $T{~1~}, ..., T{~i~}$ care este şi sufix al $T{~1~}, ..., T{~i~}$.

Gigel este interesat de prefixele $T{~1~}, ..., T{~i~}$ ale acestui şir ({$1 ≤ i ≤ N$}). El observă că un astfel de prefix de lungime $i$ are la rândul lui anume prefixe care îi sunt şi sufixe. De exemplu, dacă $T = 0101012$ şi $i = 5$, în prefixul $01010$ se găseşte prefixul $010$ care este şi sufix. Vă roagă să gasiţi pentru fiecare prefix $T{~1~}, ..., T{~i~}$ lungimea celui mai mare prefix diferit de $T{~1~}, ..., T{~i~}$ care este şi sufix al $T{~1~}, ..., T{~i~}$.

h2. Date de intrare

h2. Restricţii

* $1 ≤ n ≤ 131072$

* $1 ≤ N ≤ 131072$

* $1 ≤ Z ≤ 128$
h2. Exemplu

9906