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

Фермер Джон показує нові танцювальні рухи своїх корів!

Усі $n$ корів спочатку стоять в одну лінію, при цьому корова $i$ знаходиться на $i$-й позиції. Послідовність танцювальних рухів складається з $k$ пар позицій (a_1, b_1), (a_2, b_2), \ldots, (a_k, b_k). Протягом хвилини $i$, для i = 1, \ldots, k, корови, що знаходяться в даний момент на позиціях a_i та b_i, міняються місцями.

Та сама послідовність з $k$ обмінів потім повторюється протягом хвилин k+1, \ldots, 2k, потім знову протягом хвилин 2k + 1, \ldots, 3k, і так далі, циклічно, загалом протягом $m$ хвилин. Іншими словами:

• У хвилину $1$ корови на позиціях a_1 та b_1 міняються місцями.

• У хвилину $2$ корови на позиціях a_2 та b_2 міняються місцями.

• $\dots$

• У хвилину $k$ корови на позиціях a_k та b_k міняються місцями.

• У хвилину k + 1 корови на позиціях a_1 та b_1 міняються місцями.

• У хвилину k + 2 корови на позиціях a_2 та b_2 міняються місцями.

• і так далі.

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