23752번 - 카드 잘 섞기

준석이는 오늘도 열심히 카드를 섞고 있다.

준석이는 카드 $N$장을 가지고 있다. 카드에는 전부 X가 적혀 있고 위에서 $P$번째에 있는 카드 한 장에만 O가 적혀 있다. 준석이는 다음 $2$가지 쿼리를 열심히 수행하고 있다.

• 1 x y z: 위에서부터 $x$번째 카드부터 $y$번째 카드까지 리플셔플한다. 이 동작을 $z$번 반복한다.
• 2 x: 위에서 $x$장을 떼서 나머지 카드의 아래쪽에 둔다. 떼어낸 카드의 순서는 그대로 둔다.

리플셔플은 $N$장의 카드가 있을 때 카드를 위에서부터 $\left\lfloor(N + 1) / 2\right\rfloor$장의 카드 덩어리와 나머지 덩어리로 나눈 후 교대로 카드를 두는 방식으로 카드를 섞는 것이다. 섞기 전에 제일 위에 있었던 카드가 섞은 후에도 제일 위로 오도록 한다.

준석이는 카드를 열심히 섞다가 실수로 카드를 떨어트렸다! 준석이는 카드를 떨어트리기 직전에 O가 적힌 카드가 어디에 있었는지 알고 싶지만 엄청 게으르기 때문에 당신에게 부탁하기로 했다. 준석이를 위해서 카드가 떨어지기 전 O가 적힌 카드의 위치를 구해보자.

첫 번째 줄에 카드 수 $N$, 쿼리 수 $Q$, 카드를 섞기 전 O가 적힌 카드의 위치 $P$가 주어진다. ($1 \leq N \leq 10^{9}$, $1 \leq Q \leq 10^6$, $1 \leq P \leq N$)

두 번째 줄부터 $Q$개의 쿼리가 문제에서 언급한 형식으로 한 줄에 하나씩 주어진다.

• $1$번 쿼리에서 $z$는 $1$ 이상 $10^9$ 이하이며, $x \leq y$를 만족한다.
• $2$번 쿼리에서 $x$는 $1$ 이상 $N$ 미만이다.

카드가 떨어지기 전 O가 적힌 카드가 위에서 몇 번째에 있는지 출력한다.

카드 $6$장이 있을 때 쿼리 1 1 6 1을 처리하면

1 2 3 4 5 6 ⇒ 1 4 2 5 3 6

이 되고, 카드 $7$장이 있을 때 1 1 7 1을 처리하면

1 2 3 4 5 6 7 ⇒ 1 5 2 6 3 7 4

가 된다.