{"raw_statement":[{"iden":"problem statement","content":"There is a sequence $A = (A_0, A_1, \\dots, A_{N - 1})$ with $N = 2^{20}$ terms. Initially, every term is $-1$.\nProcess $Q$ queries in order. The $i$\\-th query $(1 \\leq i \\leq Q)$ is described by an integer $t_i$ such that $t_i = 1$ or $t_i = 2$, and another integer $x_i$, as follows.\n\n*   If $t_i = 1$, do the following in order.\n    1.  Define an integer $h$ as $h = x_i$.\n    2.  While $A_{h \\bmod N} \\neq -1$, keep adding $1$ to $h$. We can prove that this process ends after finite iterations under the Constraints of this problem.\n    3.  Replace the value of $A_{h \\bmod N}$ with $x_i$.\n*   If $t_i = 2$, print the value of $A_{x_i \\bmod N}$ at that time.\n\nHere, for integers $a$ and $b$, $a \\bmod b$ denotes the remainder when $a$ is divided by $b$."},{"iden":"constraints","content":"*   $1 \\leq Q \\leq 2 \\times 10^5$\n*   $t_i \\in { 1, 2 } \\, (1 \\leq i \\leq Q)$\n*   $0 \\leq x_i \\leq 10^{18} \\, (1 \\leq i \\leq Q)$\n*   There is at least one $i$ $(1 \\leq i \\leq Q)$ such that $t_i = 2$.\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$Q$\n$t_1$ $x_1$\n$\\vdots$\n$t_{Q}$ $x_{Q}$"},{"iden":"sample input 1","content":"4\n1 1048577\n1 1\n2 2097153\n2 3"},{"iden":"sample output 1","content":"1048577\n-1\n\nWe have $x_1 \\bmod N = 1$, so the first query sets $A_1 = 1048577$.\nIn the second query, initially we have $h = x_2$, for which $A_{h \\bmod N} = A_{1} \\neq -1$, so we add $1$ to $h$. Now we have $A_{h \\bmod N} = A_{2} = -1$, so this query sets $A_2 = 1$.\nIn the third query, we print $A_{x_3 \\bmod N} = A_{1} = 1048577$.\nIn the fourth query, we print $A_{x_4 \\bmod N} = A_{3} = -1$.\nNote that, in this problem, $N = 2^{20} = 1048576$ is a constant and not given in input."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}