Вам надається рядок \(S\) довжиною \(N\), що складається з малих літер англійського алфавіту. \(x\)-й \((1≤x≤N)\) символ \(S\) є \(S_x\) .

Для кожного \(i=1,2,…,N−1\) знайдіть максимальне невід’ємне ціле число \(l\), яке задовольняє всі наступні умови:

• \(l+i≤N\), і
• для всіх цілих \(k\) таких, що \(1≤k≤l\), виконується, що \(S_k ​ \neq S_{k+i} ​ \).

Зауважте, що \(l=0\) завжди задовольняє умови.

Обмеження

• N є таким цілим числом, що \(2≤N≤5000\).
• \(S\) — рядок довжиною \(N\), що складається з малих літер англійського алфавіту.

Формат вхідних даних

Перший рядок містить ціле число \(N\).

Другий рядок містить \(S\).

Формат вихідних даних

У вихідний потік виведіть \((N−1)\) рядок.

Рядок \(x\) \((1≤x<N)\) має містити відповідь як ціле число, коли \(i=x\).

Приклад вхідних даних

6
abcbac

Приклад вихідних даних

5
1
2
0
1

\(S= abcbac\).

• Коли \(i=1\), ми маємо \(S_1 ​ \neq S_2\) ​ ,\(S_2 ​ \neq S_3\) ​ ,… і \(S_5 ​ \neq S_6 ​ \), тому максимальне значення дорівнює \(l=5\).
• Коли \(i=2\), ми маємо \(S_1 ​ \neq S_3\) ​, але \(S_2 ​ =S_4\) ​, тому максимальне значення дорівнює \(l=1\).
• Коли \(i=3\), ми маємо \(S_1 ​ \neq S_4\) ​ і \(S_2 ​ \neq S_5\) ​, але \(S_3 ​ =S_6\) ​, тому максимальне значення дорівнює \(l=2\).
• Коли \(i=4\), ми маємо \(S_1 =S_5 \), тому максимальне значення дорівнює \(l=0\).
• Коли \(i=5\), ми маємо \(S+1 ​ \neq S_6\) ​ , тому максимальне значення дорівнює \(l=1\).