시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 1024 MB | 43 | 16 | 13 | 35.135% |
윤이는 야바위 게임에 참가하려고 한다. 야바위 게임의 규칙은 다음과 같다. 먼저 진행자는 $K$개의 컵을 일렬로 뒤집어 놓고, 참가자 앞에서 컵 하나에 구슬을 담는다. 진행자가 컵을 섞는 동작을 하면 참가자는 진행자의 동작을 잘 보고 구슬의 최종 위치를 맞혀야 한다.
진행자의 동작은 두 종류가 있다. 첫 번째는 두 컵의 위치를 바꾸는 것이다. 두 번째는 한 컵에 있는 내용물을 다른 컵으로 옮기는 것이다. 진행자는 두 가지 동작을 잘 섞어서 $N$번의 동작을 했다.
윤이는 눈이 빨라서 진행자가 어떤 동작을 하는지 전부 기억했다. 하지만 윤이는 의외의 허당이라서 진행자의 동작 하나를 놓치고 말았다. 심지어 처음에 구슬이 담겨 있던 컵의 위치마저 까먹었다. 쿼리마다 윤이가 놓친 정보들이 주어졌을 때 구슬의 최종 위치를 찾는 프로그램을 작성하시오.
첫 줄에 컵의 개수 $K$, 진행자가 수행한 동작의 수 $N$과 쿼리의 수 $M$이 주어진다.
다음 $N-1$개 줄에 윤이가 본 동작을 나타내는 정수 $t,a,b$가 순서대로 주어진다. $(t\in\{1,2\}, 1\le a,b\le K, a\ne b)$
다음 $M$개 줄에 쿼리가 주어진다. 각 쿼리마다 정수 $s, m, t, a, b$가 주어진다.
각 줄에 쿼리마다 최종적으로 구슬이 담긴 컵이 몇 번째인지 출력한다.
$2 ≤ K,N,M ≤ 300,000$
윤이가 본 야바위꾼의 동작 $N-1$개가 $t=1$인 경우만 주어진다. 윤이가 놓친 동작은 $t=1,2$ 모두 가능하다.
추가적인 제약 조건이 없다.
5 5 4 1 3 2 2 5 2 1 2 4 2 1 3 5 4 1 4 1 3 1 1 1 3 3 2 2 3 2 4 5 2 2 5
3 3 4 5
첫 번째 쿼리의 경우 구슬은 처음에 $5$번째 컵에 담겨 있다. 구슬의 위치는 다음과 같이 변한다.