prefixe

Cerință

Fie un șir de caractere $S$, format din litere mici ale alfabetului englez, indexat de la $0$. Aflați pentru fiecare $i >= 2$, cel mai mare $l$ pentru care există $0 < j < i - l + 1$ unde stringurile $[s_0s_1...s_{l-1}]$, $[s_js_{j+1}...s_{j+l-1}]$ și $[s_{i-l+1}s_{i-l+2}...s_{i}]$ sunt egale. Dacă nu există un astfel de $l$, afișați valoarea $0$.

Date de intrare

Pe prima linie se va citi un număr natural $N$ reprezentând dimensiunea șirului. Pe a doua linie se află șirul de caractere $S$.

Date de ieșire

În fişierul de ieşire se vor afişa, pe linii diferite, $N-2$ numere naturale reprezentând valorile lui $l$ pentru fiecare poziție mai mare sau egală decât 2.

Restricții și precizări

• $1 \leq N \leq 10^6$;
• Subtask $1$ ($14$p), $N \leq 50$;
• Subtask $2$ ($16$p), $N \leq 200$;
• Subtask $3$ ($35$p), $N \leq 1 \ 000$;
• Subtask $4$ ($20$p), $N \leq 100 \ 000$;
• Subtask $5$ ($15$p), $N \leq 1 \ 000 \ 000$.

Exemplul 1

stdin

10
babaaabaab

stdout

0
0
0
0
1
2
0
1

Exemplul 2

stdin

15
ldildildildqldi

stdout

0
0
0
0
1
2
3
4
5
0
1
2
3