AT_abc410_c [ABC410C] Rotatable Array

長さ $ N $ の整数列 $ A $ があり、最初 $ A_i = i $ です。 以下のクエリを全部で $ Q $ 個処理してください。 - タイプ $ 1 $ : $ A_p $ を $ x $ に変更する。 - タイプ $ 2 $ : $ A_p $ を出力する。 - タイプ $ 3 $ : 「 $ A $ の先頭の要素を末尾にする」という操作を $ k $ 回繰り返す。 - 厳密には、 $ A $ を $ (A_2,A_3,\dots,A_N,A_1) $ に置き換えることを $ k $ 回繰り返す。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ \rm{Query} $ $ _1 $ $ \rm{Query} $ $ _2 $ $ \vdots $ $ \rm{Query} $ $ _Q $ 但し、 $ \rm{Query} $ $ _i $ は $ i $ 個目のクエリを表す。 タイプ $ 1 $ のクエリは以下の形式で与えられる。 > 1 $ p $ $ x $ タイプ $ 2 $ のクエリは以下の形式で与えられる。 > 2 $ p $ タイプ $ 3 $ のクエリは以下の形式で与えられる。 > 3 $ k $

タイプ $ 2 $ のクエリが現れる度に、その解答を $ 1 $ 行に出力せよ。

### Sample Explanation 1 この入力には $ 5 $ 個のクエリが含まれます。 - 最初、 $ A=(1,2,3,4,5) $ です。 - $ 1 $ 番目のクエリはタイプ $ 2 $ で、 $ A_3=3 $ を出力します。 - $ 2 $ 番目のクエリはタイプ $ 1 $ で、 $ A_2=1000000 $ に置き換えます。 - クエリの結果、 $ A=(1,1000000,3,4,5) $ となります。 - $ 3 $ 番目のクエリはタイプ $ 3 $ で、「 $ A $ の先頭の要素を末尾にする」という操作を $ 4 $ 回繰り返します。 - クエリの結果、 $ A=(5,1,1000000,3,4) $ となります。 - $ 4 $ 番目のクエリはタイプ $ 2 $ で、 $ A_2=1 $ を出力します。 - $ 5 $ 番目のクエリはタイプ $ 2 $ で、 $ A_3=1000000 $ を出力します。 ### Sample Explanation 2 出力が空である場合もあります。 ### Constraints - 入力は全て整数 - $ 1 \le N \le 10^6 $ - $ 1 \le Q \le 3 \times 10^5 $ - 全てのクエリは以下の制約を満たす - $ 1 \le p \le N $ - $ 1 \le x \le 10^6 $ - $ 1 \le k \le 10^9 $