410767: GYM104099 5 Спорт~--- это спорт

5. Спорт — это спортограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Как известно, Кирилл — восходящий спортсмен. Он соблюдает диету, никогда не пропускает тренировки, а также ежедневно бегает по утрам на стадионе около своего дома.

Стадион, на котором бегает Кирилл, имеет форму окружности, вдоль которой равномерно рассажены $$$n$$$ деревьев, пронумерованных целыми числами от $$$1$$$ до $$$n$$$ вдоль стадиона. Каждое дерево характеризуется своим типом. Для удобства пронумеруем типы деревьев целыми числами от $$$1$$$ до $$$m$$$.

Тренер Кирилла очень суров: он требует от своих учеников фото-отчет о каждой тренировке, поэтому пробежка Кирилла проходит в следующем формате. Кирилл становится напротив первого дерева и начинает пробежку, попутно фотографируя все деревья, мимо которых он пробежал. К сожалению, памяти на телефоне Кирилла хватает лишь на $$$k$$$ фотографий. Поэтому пробежав в очередной раз мимо $$$k$$$ деревьев, мальчик вынужден остановиться, отправить некоторые из сделанных фотографий тренеру, очистить память на телефоне и продолжить пробежку. Кирилл понимает, что тренеру будет неинтересно смотреть на деревья одного и того же типа. Поэтому, если во время очередного забега Кирилл сделал несколько фотографий деревьев одного и того же типа, он отправит только одну из этих фотографий. Затем мальчик очистит память на телефоне и продолжит пробежку, начиная со следующего дерева. Так будет продолжаться, пока Кирилл не остановится, в очередной раз сделав $$$k$$$ фотографий, и не обнаружит, что следующее дерево — в точности то, с которого он начинал пробежку. После этого Кирилл отправит тренеру очередную порцию фотографий и пойдет домой.

Для лучшего понимания процесса рассмотрим следующий пример: пусть вдоль стадиона посажены шесть деревьев следующих типов: $$$1, 3, 2, 3, 2, 2$$$, а $$$k = 4$$$. Кирилл начинает пробежку и фотографирует первые $$$k$$$ деревьев, которые имеют типы $$$1$$$, $$$3$$$, $$$2$$$ и $$$3$$$. После этого Кирилл останавливается и отправляет тренеру одну фотографию дерева типа $$$1$$$, одну фотографию дерева типа $$$2$$$, и одну фотографию дерева типа $$$3$$$. После чего он очищает память телефона, становится напротив дерева с номером $$$5$$$ и продолжает пробежку. Далее Кирилл сфотографирует деревья типов $$$2$$$, $$$2$$$, $$$1$$$ и $$$3$$$, отправит тренеру по одной фотографии каждого из деревьев первого, второго, и третьего типов. Далее Кирилл пробежит вдоль деревьев с типами $$$2$$$, $$$3$$$, $$$2$$$ и $$$2$$$, и отправит тренеру одно фото дерева типа $$$2$$$ и одно фото дерева типа $$$3$$$. После этого Кирилл поймет, что следующее дерево имеет номер $$$1$$$, и пойдет домой.

Таким образом, Кирилл отправит тренеру две фотографии деревьев первого типа, три фотографии деревьев второго типа и три фотографии деревьев третьего типа.

Однажды Кириллу стало интересно, на скольких фотографиях тренер увидит дерево каждого из $$$m$$$ типов. Помогите Кириллу ответить на этот вопрос. Вычислите для каждого типа дерева $$$i$$$ количество фотографий, на которых будет представлено дерево этого типа.

Входные данные

Первая строка содержит три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$1 \le n \le 200\,000$$$, $$$1 \le m \le n$$$, $$$1 \le k \le n$$$) — количество деревьев, которые растут вдоль стадиона, количество различных типов деревьев, а также максимальное количество фотографий, на которое хватает памяти телефона Кирилла.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le m$$$) — типы деревьев.

Выходные данные

Выведите $$$m$$$ целых чисел: $$$i$$$-е число должно быть равно количеству отправленных фотографий, на которых представлено дерево $$$i$$$-го типа.

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Подзадача	Баллы	Ограничения	Необходимые подзадачи	Информация о проверке
0	0	Тесты из условия	—	полная
1	10	$$$n \le 400$$$	—	первая ошибка
2	20	$$$n \le 2\,000$$$	1	первая ошибка
3	20	$$$m \le 10$$$	—	первая ошибка
4	10	$$$k \le 10$$$	—	первая ошибка
5	40	Нет дополнительных ограничений	1 — 4	первая ошибка

ПримерыВходные данные

4 2 2
2 1 2 2

Выходные данные

1 2 

Входные данные

5 3 4
2 1 3 2 1

Выходные данные

5 5 4 

Входные данные

7 3 5
2 1 2 3 1 3 3

Выходные данные

7 7 7 

Примечание

Рассмотрим первый пример. Во время первого забега Кирилл сделает фото деревьев с номерами $$$1$$$ и $$$2$$$, а во время второго  — с номерами $$$3$$$ и $$$4$$$. После этого пробежка завершится. Фотографии деревьев второго типа Кирилл отправит два раза, а фотографию единственного дерева первого типа — только после первого забега.

Рассмотрим второй пример. Во время первого забега Кирилл сфотографирует деревья с номерами $$$1$$$, $$$2$$$, $$$3$$$ и $$$4$$$. Во время второго в телефон Кирилла попадут деревья номерами $$$5$$$, $$$1$$$, $$$2$$$ и $$$3$$$. Во время третьего — деревья с номерами $$$4$$$, $$$5$$$, $$$1$$$ и $$$2$$$. Во время четвертого — деревья с номерами $$$3$$$, $$$4$$$, $$$5$$$ и $$$1$$$. Наконец, во время пятого забега Кирилл сфотографирует деревья с номерами $$$2$$$, $$$3$$$, $$$4$$$ и $$$5$$$. Среди любых четырех посаженных подряд деревьев есть хотя бы одно дерево первого или второго типа, поэтому они будут отправлены тренеру после каждого забега. Дерево третьего типа будет отправлено после всех забегов, кроме третьего.