32174번 - 조커 찾기 2

문제

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

카드는 총 $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 = 0$이면 처음 상태의 덱으로 바꾼다.
  • 덱 시점을 되돌리는 것이 아니라, 덱 상태만 바꾸는 것임에 유의하라.

열심히 카드 섞기 기술을 연마하던 도중, 친구가 찾아와 수현이에게 카드를 $M$번 섞은 후에 조커 카드가 어디에 있는지 물어보았다. 하지만 수현이는 아직 기술을 마스터하지 못했다. 수현이를 위해, 카드 섞기 방법이 주어졌을 때 카드 섞기를 마치고 난 후 조커의 위치가 위에서부터 몇 번째 카드인지 찾아보자.

입력

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

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

출력

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

제한

• 1ドル \le N, M \le 100,000円$
• 1ドル \le x_i, y_i \le 10^{18}$
• 0ドル \le z_i \lt i$
• 1ドル \le i \le M$
• 주어지는 모든 입력은 정수이다.

힌트