Задача 5. Робот-съемщик

Задача 5. Робот-съемщик
Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Сегодня студия BBC снимает репортаж про богатую флору Воронежской области. Для этого
съемочная группа приехала в один из самых красивых парков области. В парке есть дорожка,
имеющая форму окружности, вдоль которой посажены n цветов, пронумерованных целыми числами
от 1 до n вдоль дорожки. Каждый цветок характеризуется своим типом. Для удобства пронумеруем
все типы цветов целыми числами от 1 до m.
Чтобы снять репортаж, студия использует специального робота-съемщика, который должен запечатлеть на видео красоту парка. Робот действует следующим образом: в начале репортеры устанавливают его напротив цветка с номером 1, после чего робот начинает съемку видео. Робот перемещается от первого цветка до цветка с номером k, снимая при этом все цветы с номерами 1, 2, . . . , k.
После этого запись первого видео заканчивается и робот перемещается к цветку с номером k + 1.
Далее робот начинает запись второго видео и перемещается от цветка с номером k + 1 по окружности, запечатлевая цветок с номером k + 1, а также следующие k − 1 цветов. После этого запись
второго видео заканчивается, и процесс повторяется по аналогии. Когда робот закончит снимать
очередное видео и окажется напротив цветка с номером n, репортаж завершится.
Для лучшего понимания процесса рассмотрим пример. Пусть в парке растут 6 цветов, а k = 4.
Тогда на первое видео попадут цветы с номерами 1, 2, 3 и 4. На второе видео попадут цветы с
номерами 5, 6, 1 и 2. На третье видео попадут цветы с номерами 3, 4, 5 и 6. После этого репортаж
завершится, так как робот окажется напротив цветка с номером 6.
После того, как студия запустила робота, сценаристам стало интересно, на скольких видео зритель сможет увидеть хотя бы один цветок 1-го, 2-го, ..., m-го типа.
Помогите сценаристам ответить на эти вопросы. Вычислите для каждого типа цветка i количество видео, на которых зритель сможет увидеть хотя бы один цветок i-го типа.
Формат входных данных
Первая строка содержит три целых числа n, m и k (1 <= n <= 200 000, 1 <= m <= n, 1 <= k <= n) — количество цветов в парке, количество различных типов цветов, а также количество цветов, попадающих на одно видео. Вторая строка содержит n целых чисел a1, a2, . . . , an (1 <= ai <= m) — типы цветов.
Формат выходных данных
Выведите m целых чисел через пробел: i-е число должно быть равно количеству видео, на которых зритель сможет увидеть хотя бы один цветок i-го типа.

0