Коров'ячий танець (Золото)

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

Спочатку всі n корів стоять у ряд, причому корова i займає позицію i. Танцювальні переміщення визначаються k парами позицій (a[1], b[1]), (a[2], b[2]), ..., (a[k], b[k]). Щохвилини i = 1..k корови на позиціях a[i] і b[i] міняються місцями. Ці k обмінів повторюються у хвилини k + 1..2k, потім у хвилини 2k + 1 .. 3k, і так далі, аж до завершення m хвилин. Іншими словами:

• У хвилину 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 (2 ≤ n ≤ 10^5), k (1 ≤ k ≤ 2 * 10^5), m (1 ≤ m ≤ 10^18). Кожен з наступних k рядків містить (a[1], b[1])...(a[k], b[k]) (1 ≤ a[i] < b[i] ≤ 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.

Приклади