Корови Фермера Джона танцюють.

Спочатку всі \(N\) корів (\(2\le N\le 10^5\)) стоять у ряд, корова \(i\) стоїть на позиції \(i\). Послідовність переміщень у танці задається \(K\) (\(1\le K\le 2\cdot 10^5\)) парами позицій \((a_1,b_1), (a_2,b_2), \ldots, (a_{K},b_{K})\). У кожну хвилину \(i = 1 \ldots K\) танцю, корови в позиціях \(a_i\) та \(b_i\) обмінюються позиціями. Аналогічні \(K\) обмінів відбудуться у хвилини \(K+1 \ldots 2K\), потім у хвилини \(2K+1 \ldots 3K\), і т.д. до закінчення \(M\) хвилин (\(1\le M\le 10^{18}\))

Іншими словами

• У хвилину \(1\), корови в позиціях \(a_1\) та \(b_1\) обмінюються позиціями.
• У хвилину \(2\), корови в позиціях \(a_2\) та \(b_2\) обмінюються позиціями.
• ...
• У хвилину \(K\), корови в позиціях \(a_{K}\) та \(b_{K}\) обмінюються позиціями.
• У хвилину \(K+1\), корови в позиціях \(a_{1}\) та \(b_{1}\) обмінюються позиціями.
• У хвилину \(K+2\), корови в позиціях \(a_{2}\) та \(b_{2}\) обмінюються позиціями.
• і т.д. ...

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

Зауваження: час на тест подвоєний.

Формат вхідних даних

Перший рядок містить цілі числа \(N\), \(K\), \(M\). Кожен з наступних \(K\) рядків містить \((a_1,b_1) \ldots (a_K, b_K)\) (\(1\le a_i<b_i\le N\)).

Формат вихідних даних

Виведіть \(N\) рядків. \(i\)-ий рядок містить кількість унікальних позицій, які займала корова \(i\).

Приклад вхідних даних

6 4 7
1 2
2 3
3 4
4 5

Приклад вихідних даних

5
4
3
3
3
1

Через \(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\).

ОЦІНЮВАННЯ:

• У тестах 1-5 \(N\le 100, K\le 200\).
• У тестах 6-10 \(M=10^{18}\).
• У тестах 11-20 немає додаткових обмежень.