Флюорография
На флюорографическое обследование пришли n марсиан, представляющих k различных полов. Все они выстроились в очередь. В кабинет флюорографии допускают по m человек одновременно, но только если они одного пола. Если первым в очереди стоит представитель пола s, то запускают его и следующих m-1 представителей того же пола s, даже если между ними находятся представители других полов. Если представителей данного пола в очереди осталось меньше, чем m, то в кабинет заходят все оставшиеся, а представители других полов продолжают ждать. Каждая следующая группа марсиан заходит через час после предыдущей, даже если предыдущая группа была меньше m человек.
Зная порядок, в котором представители всех полов стоят в очереди, определите для каждого из них, через сколько часов после начала обследования он попадёт в кабинет флюорографии.
Входные данные
В первой строке входного файла указаны количество марсиан в очереди n, количество полов k и максимальный размер группы m. Все три числа натуральные и не превышают 100000. Во второй строке заданы n чисел, разделённых пробелами. Число на i-м месте — пол лица, стоящего i-м в очереди. Пол задан натуральным числом от 1 до k включительно.
В 40% тестов для этой задачи n, k и m не превышают 1000, а ещё в 20% тестов k не больше 10.
Выходные данные
Выходной файл должен содержать n чисел, разделённых пробелами. Число на i-м месте — количество часов после начала обследования, когда i-е лицо из очереди попадёт в кабинет флюорографии.