Pride of Sniper

アズサ

ヒフミちゃんの期待に応えられるよう、頑張らないとな。……状況を整理してみよう。

• $x$軸は、$1$番の実と$\frac{N}{2} + 1$番の実を結ぶ直線。
• $y$軸は、$x$軸に垂直で、私の立つ射撃位置、つまり円の中心を通る直線。

実は円の上に等間隔に置かれているので、どの実についても、$x$軸や$y$軸に関して対称な位置には、必ずちょうど1つの別の実がある。

サブクエリ

先生が用意したプログラムには、$1$番から$M$番までの番号がついた、計$M$個のサブクエリがある。各サブクエリは、現在選択されている実をどの実に変更するかを表す命令で、次の4つの形式のいずれかだ。

• 1 a: 現在選択されている実から、反時計回りに$a$個分進んだ位置の実を選択する。
• 2 a: 現在選択されている実から、時計回りに$a$個分進んだ位置の実を選択する。
• 3: 現在選択されている実と、$x$軸に関して対称な位置の実を選択する。
• 4: 現在選択されている実と、$y$軸に関して対称な位置の実を選択する。

移動は円環状につながっている。反時計回りに$1$個分進むと、$N$番の実からは$1$番の実に戻り、それ以外では$i$番から$i+1$番へ移動する。同様に、時計回りに$1$個分進むと、$1$番からは$N$番へ、それ以外では$i$番から$i-1$番へ移動する。

……だが、先生はサブクエリを1つずつ実行するだけではないようだ。

クエリ

この$M$個のサブクエリを実行したり、その内容自体を変更したりするため、プログラムにはさらに$Q$個のクエリがある。各クエリは次の2種類のいずれかだ。

• 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 クエリの終了後は、新たに選択された実をそのまま選択した状態で、次のクエリを実行することに注意しよう。

目標

うん、分かった。結局、知りたいことはただ1つ。

「先生が読み上げるヤシの実の番号は、順番に何になるだろう？」

先に番号が分かっていれば有利なはずだ。与えられたすべてのクエリをそのまま実行したときの番号を、順に求めよう。

2行目から$M+1$行目には、$1$番から$M$番までのサブクエリが、番号順に1行ずつ与えられる。各行は次の2つの形式のいずれかである。

• 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行ずつ与えられる。各行は次の3つの形式のいずれかである。$(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$のクエリは少なくとも1回与えられる。

実行時間制限

2000 ms

メモリ制限

1024 MB

チェッカー

CUSTOM