{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eYou 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**.\u003cbr\u003e\u003cbr\u003eMoreover, there are $m$ instructions.\u003cbr\u003e\u003cbr\u003eEach instruction is in one of the following two formats:\u003cbr\u003e\u003cbr\u003e1. $(1,pos)$,indicating to change the value of $a_{pos}$ to $a_{pos}+10,000,000$;\u003cbr\u003e2. $(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$.\u003cbr\u003e\u003cbr\u003ePlease print all results of the instructions in format $2$.\u003cbr\u003e\u003cbr\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line of the input contains an integer $T(1 \\leq T \\leq 10)$, denoting the number of test cases.\u003cbr\u003e\u003cbr\u003eIn 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.\u003cbr\u003e\u003cbr\u003eIn 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.\u003cbr\u003eFor the following $m$ lines, each line is of format $( 1 , t1 )$ or $( 2 , t2 , t3 )$.\u003cbr\u003eThe parameters of each instruction are generated by such way :\u003cbr\u003e\u003cbr\u003e For instructions in format $1$ , we defined $pos \u003d t1 \\oplus LastAns$ . (It is promised that $1 \\leq pos \\leq n$)\u003cbr\u003e\u003cbr\u003e For instructions in format $2$ , we defined $r \u003d t2 \\oplus LastAns , k \u003d t3 \\oplus LastAns$. (It is promised that $1 \\leq r \\leq n , 1 \\leq k \\leq n$ )\u003cbr\u003e\u003cbr\u003e (Note that $\\oplus$ means the bitwise XOR operator. )\u003cbr\u003e\u003cbr\u003e 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.\u003cbr\u003e\u003cbr\u003e($\\sum n \\leq 510,000 , \\sum m \\leq 510,000 $ )"}},{"title":"Output","value":{"format":"HTML","content":"For each instruction in format $2$, output the answer in one line."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n5 9\r\n4 3 1 2 5 \r\n2 1 1\r\n2 2 2\r\n2 6 7\r\n2 1 3\r\n2 6 3\r\n2 0 4\r\n1 5\r\n2 3 7\r\n2 4 3\r\n10 6\r\n1 2 4 6 3 5 9 10 7 8 \r\n2 7 2\r\n1 2\r\n2 0 5\r\n2 11 10\r\n1 3\r\n2 3 2\r\n10 10\r\n9 7 5 3 4 10 6 2 1 8 \r\n1 10\r\n2 8 9\r\n1 12\r\n2 15 15\r\n1 12\r\n2 1 3\r\n1 9\r\n1 12\r\n2 2 2\r\n1 9\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n5\r\n2\r\n2\r\n5\r\n6\r\n1\r\n6\r\n7\r\n3\r\n11\r\n10\r\n11\r\n4\r\n8\r\n11\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cbr\u003enote:\u003cbr\u003eAfter the generation procedure ,the instructions of the first test case are :\u003cbr\u003e2 1 1, in format 2 and r\u003d1 , k\u003d1\u003cbr\u003e2 3 3, in format 2 and r\u003d3 , k\u003d3\u003cbr\u003e2 3 2, in format 2 and r\u003d3 , k\u003d2\u003cbr\u003e2 3 1, in format 2 and r\u003d3 , k\u003d1\u003cbr\u003e2 4 1, in format 2 and r\u003d4 , k\u003d1\u003cbr\u003e2 5 1, in format 2 and r\u003d5 , k\u003d1\u003cbr\u003e1 3 , in format 1 and pos\u003d3\u003cbr\u003e2 5 1, in format 2 and r\u003d5 , k\u003d1\u003cbr\u003e2 5 2, in format 2 and r\u003d5 , k\u003d2\u003cbr\u003e\u003cbr\u003ethe instructions of the second test case are :\u003cbr\u003e2 7 2, in format 2 and r\u003d7 , k\u003d2\u003cbr\u003e1 5 , in format 1 and pos\u003d5\u003cbr\u003e2 7 2, in format 2 and r\u003d7 , k\u003d2\u003cbr\u003e2 8 9, in format 2 and r\u003d8 , k\u003d9\u003cbr\u003e1 8 , in format 1 and pos\u003d8\u003cbr\u003e2 8 9, in format 2 and r\u003d8 , k\u003d9\u003cbr\u003e\u003cbr\u003ethe instructions of the third test case are :\u003cbr\u003e1 10 , in format 1 and pos\u003d10\u003cbr\u003e2 8 9 , in format 2 and r\u003d8 , k\u003d9\u003cbr\u003e1 7 , in format 1 and pos\u003d7\u003cbr\u003e2 4 4 , in format 2 and r\u003d4 , k\u003d4\u003cbr\u003e1 8 , in format 1 and pos\u003d8\u003cbr\u003e2 5 7 , in format 2 and r\u003d5 , k\u003d7\u003cbr\u003e1 1 , in format 1 and pos\u003d1\u003cbr\u003e1 4 , in format 1 and pos\u003d4\u003cbr\u003e2 10 10, in format 2 and r\u003d10 , k\u003d10\u003cbr\u003e1 2 , in format 1 and pos\u003d2\u003cbr\u003e"}}]}