# Round And Round

Time Limit : 2 sec, Memory Limit : 524288 KB

# Problem C: Round And Round

## Problem

$N$̐$A=\{a_{1},a_{2},a_{3},...,a_{n}\}$^B
$a_{i}$ ($i=1,2,3,...,n$)́A$i$ŏĂ̂ƂB

ȉ̓ނ̃NGv$Q$񏈗B

• $A$̐擪$k$Ԗڂ̗vf̒lo͂B
• $A$̐擪$k$$k+1ԖڂEɓ̐XbvB ڂ̓Tvo͂QlɂB ## Input ͈͂ȉ̌ŗ^B N Q query_1 query_2 ... query_Q  eNG͈ȉ̓ނ̂ꂩ̌ŗ^B NG0 0 k A̐擪kԖڂ̗vf̒lo͂B NG1 1 k A̐擪k$$k+1$ԖڂEɓ̐XbvB

ׂ͂͂Đŗ^B

$1$sڂ$N$, $Q$󔒋؂ŗ^B
$2$sڈȍ~$Q$sɃNGs؂ŗ^B
eNG̐l͑Sċ󔒋؂łB

## Constraints

͈͂ȉ̏𖞂B

• $2 \leq N \leq 10^9$
• $1 \leq Q \leq 10^5$

eNGɂāA͈͂ȉ̏𖞂B

NG$0$
• $1 \leq k \leq N$

• NG$1$
• $1 \leq k \leq N-1$

## Output

eNG$1$ɑ΂lsɏo͂B

## Sample Input 1

5 4
1 2
0 2
1 1
0 3


## Sample Output 1

4
1

$5$̐$A=[1,2,3,4,5]$^
$1$Ԗڂ̃NG $[1,2,3,4,5]$ -> $[1,2] [3,4,5]$ -> $[3,4,5] [1,2]$ -> $[3,4,5,1,2]$ Ɛ񂪕ωB
$2$Ԗڂ̃NGŐ擪$2$Ԗڂ̗vf̒lł$4$o͂B
$3$Ԗڂ̃NG $[3,4,5,1,2]$ -> $[3] [4,5,1,2]$ -> $[4,5,1,2] [3]$ -> $[4,5,1,2,3]$ Ɛ񂪕ωB
$4$Ԗڂ̃NGŐ擪$3$Ԗڂ̗vf̒lł$1$o͂B

## Sample Input 2

4 4
1 2
1 1
0 1
0 4


## Sample Output 2

4
3


## Sample Input 3

10 6
1 1
0 1
1 9
0 5
1 1
0 10


## Sample Output 3

2
5
1