조커 찾기 2

면접 대비

시간 제한1초메모리 제한1024 MB

요약

맨 위 카드와 맨 아래 카드를 옮기는 연산과 이전 덱 상태를 가리키는 연산이 주어질 때, 처음 1번에 있던 조커의 마지막 위치를 구합니다.

문제

중앙대학교에 다니는 수현이는 타짜 기술을 습득하였다. 이번에는 유튜브에서 마술 영상을 보고 따라 하고 싶어진 수현이가 카드 덱 맨 위에 조커를 올려두고, 카드를 섞어 조커를 원하는 위치로 보내려 한다.

카드는 총 $N$ 장이며, 백지 카드 $N-1$ 장과 조커 카드 $1$ 장으로 구성되어 있다. 맨 위 카드를 1번, 맨 아래 카드를 $N$ 번이라고 하자. 처음 상태의 덱에서는 조커가 1번 위치에 있다.

수현이는 카드를 $M$ 번 섞으려고 한다. 카드를 섞는 방법은 3가지가 있다.

1 $x_i$ : $N$ 번 카드를 1번 카드 위로 옮긴다. 이 과정을 $x_i$ 번 반복한다.
2 $y_i$ : 1번 카드를 $N$ 번 카드 밑으로 옮긴다. 이 과정을 $y_i$ 번 반복한다.
3 $z_i$ $z_{i}$ : 덱 상태를 처음 상태 이후 $z_i$ 번 섞은 뒤의 덱 상태로 바꾼다. 단, $z_i = 0$ $z_{i} = 0$ 이면 처음 상태의 덱으로 바꾼다.
- 덱의 시점을 되돌리는 것이 아니라, 덱 상태만 바꾸는 것임에 유의하라.

첫 번째 줄에 $N$ 과 $M$ 이 공백으로 구분되어 주어진다.

그다음 줄부터 $M$ 개의 줄에 걸쳐 카드 섞는 방법이 주어진다. 그중 $i$ 번째 줄에는 $i$ 번째 카드 섞는 방법이 주어진다.

카드 섞기를 완료했을 때 조커가 덱의 맨 위에서 몇 번째에 있는지 출력한다.