J - Reverse Array Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 6 点

注意

この問題に対する言及は、2021/10/02 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

長さ 2N の数列 A = (1,2, \ldots ,2N) があります。Q 個のクエリを処理してください。i 番目のクエリでは、整数 t_i, k_i が与えられます。

  • t_i = 1 のとき : 数列 A の左から k_i 番目の要素の値を出力する。
  • t_i = 2 のとき : 数列 A の中央の 2k_i 個の要素の順序を反転させる。つまり、左から N-k_i+1 番目の要素から左から N+k_i 番目の要素までの順序を反転させる。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq t_i \leq 2
  • t_i=1 なる i が 1 つ以上存在する。
  • t_i=1 ならば 1 \leq k_i \leq 2N
  • t_i=2 ならば 1 \leq k_i \leq N
  • 入力は全て整数である。

入力

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

N Q
t_1 k_1
t_2 k_2
\vdots
t_Q k_Q

出力

t_i=1 をみたす i について、それぞれ数列 A の左から k_i 番目の要素の値を改行区切りで出力せよ。

入力例 1

3 2
2 2
1 4

出力例 1

3

はじめ数列 A は (1,2,3,4,5,6) です。

1 つ目のクエリでは、中央の 4 要素を反転させ、数列 A は (1,5,4,3,2,6) となります。

2 つ目のクエリでは、左から 4 番目の要素は 3 なので、3 と出力してください。

入力例 2

3 3
2 3
1 3
1 1

出力例 2

4
6

入力例 3

5 6
2 2
2 1
2 1
2 3
1 2
2 3

出力例 3

2

Score : 6 points

Warning

Do not make any mention of this problem until October 2, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

We have a sequence of length 2N: A = (1,2, \ldots ,2N). Process Q queries. In the i-th query, you are given integers t_i and k_i.

  • If t_i = 1: print the value of the k_i-th element of the sequence A from the left.
  • If t_i = 2: reverse the order of the 2k_i elements at the center of the sequence A. In other words, reverse the order of the (N-k_i+1)-th through (N+k_i)-th elements from the left.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq t_i \leq 2
  • There is at least one index i such that t_i=1.
  • 1 \leq k_i \leq 2N if t_i=1.
  • 1 \leq k_i \leq N if t_i=2.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N Q
t_1 k_1
t_2 k_2
\vdots
t_Q k_Q

Output

For each i such that t_i=1, print the value of the k_i-th element of the sequence A from the left, in its own line.

Sample Input 1

3 2
2 2
1 4

Sample Output 1

3

Initially, the sequence A is (1,2,3,4,5,6).

In the first query, we reverse the middle four elements, making A = (1,5,4,3,2,6).

In the second query, the fourth element from the left is 3, so you should print 3.

Sample Input 2

3 3
2 3
1 3
1 1

Sample Output 2

4
6

Sample Input 3

5 6
2 2
2 1
2 1
2 3
1 2
2 3

Sample Output 3

2