eolymp
bolt
Try our new interface for solving problems
Problems

Флюорографія

Флюорографія

Time limit 1 second
Memory limit 32 MiB

На флюорографічне обстеження зібралися n марсіан k різних статей. Усі обсте­жу­вані певним чином вишикувалися в чергу. У кабінет флюорографії запускають по m осіб одразу, але лише якщо вони однієї статі. Якщо перша на даний момент особа в черзі має стать s, запускають цю особу, а також наступних m-1 представника статі s із черги, навіть якщо перед кимось із них стояли представники інших статей. Якщо в черзі лишилося менше ніж m представників даної статі, в кабінет запускають їх усіх, а представники інших статей мають чекати. Кожна група марсіан, починаючи з другої, заходить через годину після попередньої (навіть якщо попередня група склада­лася менше ніж із m обстежуваних).

Знаючи, в якому порядку представники всіх статей вишикувалися в чергу, визначте для кожної особи, через скільки годин після початку обстеження вона зайде в кабінет флюорографії.

Input data

У першому рядку вхідного файлу вказано кількість марсіан у черзі n, кількість статей k і максимальний розмір групи m. Усі три числа натуральні та не перевищують 100000. У другому рядку задано n чисел, розділених символами пропуску. Число на i-му місці — стать особи, що стоїть i-ю в черзі. Стать задано натуральним числом від 1 до k включно.

У 40% тестів до цієї задачі n, k та m не перевищують 1000, а ще в 20% тестів k не більше за 10.

Output data

Вихідний файл повинен містити n чисел, розділених символами пропуску. Число на i-му місці — кількість годин після початку обстеження, коли i-та особа з черги потрапить у кабінет флюорографії.

Examples

Input example #1
3 2 2
1 2 1
Output example #1
0 1 0