{"problem":{"name":"Linear Probing","description":{"content":"There is a sequence $A = (A_0, A_1, \\dots, A_{N - 1})$ with $N = 2^{20}$ terms. Initially, every term is $-1$. Process $Q$ queries in order. The $i$\\-th query $(1 \\leq i \\leq Q)$ is described by an in","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc228_d"},"statements":[{"statement_type":"Markdown","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$.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$Q$\n$t_1$ $x_1$\n$\\vdots$\n$t_{Q}$ $x_{Q}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc228_d","tags":[],"sample_group":[["4\n1 1048577\n1 1\n2 2097153\n2 3","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."]],"created_at":"2026-03-03 11:01:14"}}