Задається рядок, що містить \(n\) слів.

Для кожного слова визначiть, скiльки разiв це сллово зустрiчалась у рядку раніше (рядок переглядаться зліва направо).

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

У першому рядку вхiдного потоку міститься цiле число \(n\) (\(1 \le n \le 10^5\)).

У другому рядку задається рядок, що містить літери проміжку ['a'..'z']. Довжина рядка не перевищує \(10^5\).

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

Виведiть n цiлих чисел в окремих рядках — вiдповiдi на завдання.

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

7
one two one tho two one three

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

0
0
1
0
1
2
0