Informatica Online Judge

  House of Cards [1918 / 077E]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 3   Total Tried : 4


The Champion of this Problem (C++) : gs16103 - 0ms / 388byte
My Best Submission (C++) : N/A

[koistudy.net (34th 노규민)]
Writer ID : [gs16030]

Background

규민이에게는 $N$개의 카드가 있고, 각각 $1, 2, .... N$이라는 숫자가 적혀있다.
규민이는 이 $N$개의 카드를 하나의 덱으로 만들고, 번호가 작을 수록 위에 있도록 덱을 정리해 놓았다.

규민이는 $(u,v)$-shuffle이라는 셔플 기술을 알고 있다.
$(u,v)$-shuffle이란, $uv$개의 카드를 가지고 있을 때, 위에서부터 $u$장을 빼서 하나의 덱을 만들고,
그 다음 다시 $u$장을 빼서 두 번째 덱을 만들고 이를 반복하여 총 $v$개의 덱을 만든 뒤,
첫 번째 덱의 맨 위에 있는 카드, 두 번째 덱의 맨 위에 있는 카드, ... $v$번째 덱의 맨 위에 있는 카드를 다시 순서대로 가져가서 먼저 가져간 카드가 위에 가도록하는 것을 $u$번 반복하여 새로운 덱을 만드는 것이다.

예를 들어, 8개의 카드로 (2,4)-shuffle을 한다고 가정하자.
위에서부터 1, 2, 3, 4, 5, 6, 7, 8 순으로 카드가 있다면, 처음에 1, 2 덱, 3, 4 덱, 5, 6 덱, 7, 8 덱으로 총 4개의 덱을 만든 뒤, 1, 3, 5, 7, 2, 4, 6, 8 순으로 다시 덱을 만드는 것이다.
즉, (2,4)-shuffle의 결과는 1, 3, 5, 7, 2, 4, 6, 8이다.

관영이는 규민이의 인생을 힘들게 하기 위해, 규민이가 여러 번 $(u,v)$-shuffle들을 한 이후 덱의 최종 상태를 빠르게 구하고 싶다.
관영이를 도와주자.

Input

첫째 줄에는 카드의 개수인 $N$과 셔플의 횟수인 $Q$가 입력된다. $2 le N le 1000000, 1 le Q le 200000$
25%의 데이터에 대하여, $2 le N, Q le 1000$이 성립한다.
두 번째 줄 부터 $Q+1$번째 줄까지는, 셔플 방법을 의미하는 $u_i, v_i$가 입력된다. 단, $u_i$와 $v_i$의 곱은 항상 $N$임이 보장된다.

Output

맨 처음 $1, 2, ... N$ 순으로 정렬된 덱을 $Q$번 셔플했을 때 덱의 최종 상태를 출력한다.
즉, 덱의 가장 위에 있는 카드에 적힌 숫자부터 가장 아래에 있는 카드에 적힌 숫자까지 총 $N$개의 숫자를 차례대로 출력한다.

IO Example

예시 입력
8 1
2 4

예시 출력
1 3 5 7 2 4 6 8

예시 입력
12 3
6 2
4 3
2 6

예시 출력
1 5 9 2 6 10 3 7 11 4 8 12

예시 출력 설명
1 2 3 4 5 6 7 8 9 10 11 12 -> 1 7 2 8 3 9 4 10 5 11 6 12 -> 1 3 5 7 9 11 2 4 6 8 10 12 -> 1 5 9 2 6 10 3 7 11 4 8 12

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]