Pride of Sniper

아즈사

히후미 쨩의 기대에 부응할 수 있도록 열심히 해야지. ……상황을 한 번 정리해 보자.

• $x$축은 $1$번 열매와 $\frac{N}{2} + 1$번 열매를 잇는 직선.
• $y$축은 $x$축과 수직이고, 내가 서 있는 사격 위치(원의 중심)를 지나는 직선.

야자열매는 원 위에 균일하게 놓여 있으니까, 어느 열매든 $x$축이나 $y$축에 대해 대칭인 위치에도 항상 정확히 하나의 다른 열매가 존재할 거야.

서브 쿼리

선생님이 준비한 프로그램에는 서브 쿼리가 총 $M$개 있고, 각각 $1$번부터 $M$번까지 번호가 붙어 있어. 각 서브 쿼리는 현재 선택된 야자열매를 어느 다른 야자열매로 바꿀지를 나타내는 명령이고, 다음 네 가지 형태 중 하나야.

• 1 a: 지금 선택된 열매에서 반시계 방향으로 $a$만큼 이동한 위치의 열매를 선택.
• 2 a: 지금 선택된 열매에서 시계 방향으로 $a$만큼 이동한 위치의 열매를 선택.
• 3: 지금 선택된 열매와 $x$축에 대해 대칭인 위치의 열매를 선택.
• 4: 지금 선택된 열매와 $y$축에 대해 대칭인 위치의 열매를 선택.

이동은 원 모양으로 이어져 있어서, 반시계 방향으로 $1$만큼 이동하면 $N$번 열매에서 $1$번 열매로 돌아오고, 그 외에는 $i$번 열매에서 $i+1$번 열매로 이동할 거야. 마찬가지로 시계 방향으로 $1$만큼 이동하면 $1$번 열매에서 $N$번 열매로, 그 외에는 $i$번 열매에서 $i-1$번 열매로 이동할 거고.

……하지만, 선생님은 서브 쿼리 하나만 실행하는 것이 아니네.

쿼리

프로그램은 이 $M$개의 서브 쿼리를 실행하거나 내용 자체를 바꾸기 위해, 추가로 $Q$개의 쿼리가 존재해. 각 쿼리는 다음 두 종류 중 하나야.

• 1 i j: $i$번 서브 쿼리부터 $j$번 서브 쿼리까지, 번호가 작은 것부터 차례대로 모두 실행.

• 2 i j q 또는 2 i j q a: $i$번 서브 쿼리부터 $j$번 서브 쿼리까지를, 전부 똑같은 서브 쿼리로 내용을 변경.

  • $q = 1$: 2 i j q a 형태로 주어지고, 해당 구간의 서브 쿼리를 모두 1 a로 변경.
  • $q = 2$: 2 i j q a 형태로 주어지고, 해당 구간의 서브 쿼리를 모두 2 a로 변경.
  • $q = 3$: 2 i j q 형태로 주어지고, 해당 구간의 서브 쿼리를 모두 3으로 변경.
  • $q = 4$: 2 i j q 형태로 주어지고, 해당 구간의 서브 쿼리를 모두 4로 변경.

처음에는 $S$번 야자열매가 선택되어 있다고 하네? 이 상태에서 $Q$개의 쿼리를 앞에서부터 순서대로 수행할 테고. 각 1 i j 쿼리가 모두 끝날 때마다, 선생님은 그 순간 선택된 야자열매의 번호를 불러 줄 거야.

각 1 i j 쿼리가 종료되고 새롭게 선택된 야자열매 그대로 다음 쿼리를 실행하는 것에 유의해야 해.

목표

응. 알겠어. 결국 내가 알고 싶은 건 단 하나.

“선생님이 부르게 되는 야자열매의 번호가 순서대로 무엇이 될까?”

미리 그 번호를 알고 있다면 유리할 터, 주어진 모든 쿼리를 그대로 따라갔을 때 그 번호들을 차례대로 구해 보자.

두 번째 줄부터 $M+1$번째 줄까지, $1$번 서브 쿼리부터 $M$번 서브 쿼리까지가 번호 순서대로 한 줄에 하나씩 주어진다. 각 줄은 다음 두 형태 중 하나이다.

• t a $(1 \le t \le 2$; $1 \le a \le N-1)$
• t $(3 \le t \le 4)$

그다음 $M+2$번째 줄부터 $M+Q+1$번째 줄까지, 쿼리가 수행 순서대로 한 줄에 하나씩 주어진다. 각 줄은 다음 세 형태 중 하나이다. $(1 \le i \le j \le M$; $1 \le q \le 4$; $1 \le a \le N-1)$

• 1 i j
• 2 i j q
• 2 i j q a

$1$번 쿼리는 적어도 한 번 이상 주어진다.

시간 제한

2000 ms

메모리 제한

1024 MB

체커

CUSTOM