F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

array

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 3766    Accepted Submission(s): 1383


Problem Description
You are given an array $a_1,a_2,...,a_n (\forall i \in [1, n], 1 \leq a_i\leq n)$. Initially, each element of the array is **unique**.

Moreover, there are $m$ instructions.

Each instruction is in one of the following two formats:

1. $(1,pos)$,indicating to change the value of $a_{pos}$ to $a_{pos}+10,000,000$;
2. $(2,r,k)$,indicating to ask the minimum value which is **not equal** to any $a_i$ ( $1 \leq i \leq r$ ) and **not less ** than $k$.

Please print all results of the instructions in format $2$.

 

Input
The first line of the input contains an integer $T(1 \leq T \leq 10)$, denoting the number of test cases.

In each test case, there are two integers $n(1 \leq n \leq 100,000)$,$m(1 \leq m \leq 100,000)$ in the first line, denoting the size of array $a$ and the number of instructions.

In the second line, there are $n$ distinct integers $a_1,a_2,...,a_n$ $(\forall i \in [1, n], 1 \leq a_i\leq n)$,denoting the array.
For the following $m$ lines, each line is of format $( 1 , t1 )$ or $( 2 , t2 , t3 )$.
The parameters of each instruction are generated by such way :

For instructions in format $1$ , we defined $pos = t1 \oplus LastAns$ . (It is promised that $1 \leq pos \leq n$)

For instructions in format $2$ , we defined $r = t2 \oplus LastAns , k = t3 \oplus LastAns$. (It is promised that $1 \leq r \leq n , 1 \leq k \leq n$ )

(Note that $\oplus$ means the bitwise XOR operator. )

Before the first instruction of each test case, $LastAns$ is equal to $0$ .After each instruction in format $2$, $LastAns$ will be changed to the result of that instruction.

($\sum n \leq 510,000 , \sum m \leq 510,000 $ )
 

Output
For each instruction in format $2$, output the answer in one line.
 

Sample Input
3 5 9 4 3 1 2 5 2 1 1 2 2 2 2 6 7 2 1 3 2 6 3 2 0 4 1 5 2 3 7 2 4 3 10 6 1 2 4 6 3 5 9 10 7 8 2 7 2 1 2 2 0 5 2 11 10 1 3 2 3 2 10 10 9 7 5 3 4 10 6 2 1 8 1 10 2 8 9 1 12 2 15 15 1 12 2 1 3 1 9 1 12 2 2 2 1 9
 

Sample Output
1 5 2 2 5 6 1 6 7 3 11 10 11 4 8 11
 

Hint

note:
After the generation procedure ,the instructions of the first test case are :
2 1 1, in format 2 and r=1 , k=1
2 3 3, in format 2 and r=3 , k=3
2 3 2, in format 2 and r=3 , k=2
2 3 1, in format 2 and r=3 , k=1
2 4 1, in format 2 and r=4 , k=1
2 5 1, in format 2 and r=5 , k=1
1 3 , in format 1 and pos=3
2 5 1, in format 2 and r=5 , k=1
2 5 2, in format 2 and r=5 , k=2

the instructions of the second test case are :
2 7 2, in format 2 and r=7 , k=2
1 5 , in format 1 and pos=5
2 7 2, in format 2 and r=7 , k=2
2 8 9, in format 2 and r=8 , k=9
1 8 , in format 1 and pos=8
2 8 9, in format 2 and r=8 , k=9

the instructions of the third test case are :
1 10 , in format 1 and pos=10
2 8 9 , in format 2 and r=8 , k=9
1 7 , in format 1 and pos=7
2 4 4 , in format 2 and r=4 , k=4
1 8 , in format 1 and pos=8
2 5 7 , in format 2 and r=5 , k=7
1 1 , in format 1 and pos=1
1 4 , in format 1 and pos=4
2 10 10, in format 2 and r=10 , k=10
1 2 , in format 1 and pos=2
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-04-16 00:40:23, Gzip enabled