Коровы Фермера Джона танцуют.

Сначала все n коров стоят в ряд, корова i стоит на позиции i. Последовательность перемещений в танце задаётся k парами позиций (a1, b1), (a2, b2),...,(ak, bk). В каждую минуту i = 1..k танца, коровы в позициях ai и bi меняются позициями. Аналогичные k обменов произойдут в минуты k + 1..2k, затем в минуты 2k + 1 .. 3k, и т.д. до истечения m минут Другими словами

• В минуту 1, коровы в позициях a1 и b1 меняются позициями.
• В минуту 2, коровы в позициях a2 и b2 меняются позициями.
• ...
• В минуту k, коровы в позициях ak и bk меняются позициями.
• В минуту k + 1, коровы в позициях a1 и b1 меняются позициями.
• В минуту k + 2, коровы в позициях a2 и b2 меняются позициями.
• и т.д. ...

Для каждой коровы определите количество уникальных позиций, которые она занимала во время танца.

Замечание: время на тест удвоено.

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

Первая строка содержит целые числа n (2 ≤ n ≤ 105), k (1 ≤ k ≤ 2 * 105), m (1 ≤ m ≤ 1018). Каждая из последующих k строк содержит (a1, b1)...(ak, bk) (1 ≤ ai < bi ≤ n).

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

Выведите n строк. i-ая строка содержит количество уникальных позиций, которые занимала корова i.

Пример

Через 7 минут, коровы в порядке возрастания позиций разместятся так: [3, 4, 5, 2, 1, 6].

• Корова 1 достигнет позиций {1, 2, 3, 4, 5}.
• Корова 2 достигнет позиций {1, 2, 3, 4}.
• Корова 3 достигнет позиций {1, 2, 3}.
• Корова 4 достигнет позиций {2, 3, 4}.
• Корова 5 достигнет позиций {3, 4, 5}.
• Корова 6 никуда не двигалась, поэтому она останется в позиции 6.