C - Rotatable Array Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

長さ 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 回繰り返す。

制約

  • 入力は全て整数
  • 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

入力

入力は以下の形式で標準入力から与えられる。

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 行に出力せよ。

入力例 1

5 5
2 3
1 2 1000000
3 4
2 2
2 3

出力例 1

3
1
1000000

この入力には 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 を出力します。

入力例 2

1000000 2
1 1000000 999999
3 1000000000

出力例 2




出力が空である場合もあります。






Score : 300 points







Problem Statement
There is an integer sequence A of length N, initially A_i = i.
Process a total of Q queries of the following types:


    

  • Type 1: Change A_p to x.
    • 

  • Type 2: Output A_p.
    • 

  • Type 3: Repeat the operation "move the first element of A to the end" k times.
      

    • Formally, replace A with (A_2,A_3,\dots,A_N,A_1) k times.
      • 

    

    • 












Constraints
    

  • All input values are integers.
    • 

  • 1 \le N \le 10^6
    • 

  • 1 \le Q \le 3 \times 10^5
    • 

  • All queries satisfy the following constraints:
      

    • 1 \le p \le N
      • 

    • 1 \le x \le 10^6
      • 

    • 1 \le k \le 10^9
      • 

    

    • 
















Input
The input is given from Standard Input in the following format:


N Q
\rm{Query}_1
\rm{Query}_2
\vdots
\rm{Query}_Q




Here, \rm{Query}_i represents the i-th query.


Type 1 queries are given in the following format:


1 p x




Type 2 queries are given in the following format:


2 p




Type 3 queries are given in the following format:


3 k













Output
For each Type 2 query, output the answer on a line.















Sample Input 1
5 5
2 3
1 2 1000000
3 4
2 2
2 3













Sample Output 1
3
1
1000000




This input contains 5 queries.


    

  • Initially, A=(1,2,3,4,5).
    • 

  • The 1st query is Type 2: output A_3=3.
    • 

  • The 2nd query is Type 1: replace A_2 with 1000000.
      

    • After the query, A=(1,1000000,3,4,5).
      • 

    

    • 

  • The 3rd query is Type 3: repeat the operation "move the first element of A to the end" 4 times.
      

    • After the query, A=(5,1,1000000,3,4).
      • 

    

    • 

  • The 4th query is Type 2: output A_2=1.
    • 

  • The 5th query is Type 2: output A_3=1000000.
    • 














Sample Input 2
1000000 2
1 1000000 999999
3 1000000000













Sample Output 2



The output may be empty.