Fie un șir de caractere S format din litere mici ale alfabetului englez, indexat de la 0.

Cerința

Aflați pentru fiecare i ≥ 2 cel mai mare l pentru care există 0 < j < i − l + 1 unde stringurile \( [{s}_{0}{s}_{1}…{s}_{l-1}] \), \( [{s}_{j}{s}_{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 a intrării standard se află un număr natural N reprezentând dimensiunea șirului. Pe a doua linie se află șirul de caractere S.

Date de ieșire

La ieșirea standard 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 ≤ n ≤ 1.000.000

Exemplul 1:

Intrare

10
babaaabaab

Ieșire

0
0
0
0
1
2
0
1

Exemplul 2:

Intrare

15
ldildildildqldi

Ieșire

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