题目描述

强哥管理着一个巨大的数字仓库，仓库长度 $N$ = $2^{20}$ ，有 $2^{20}$ 个位置（编号 $0$ 到 $2^{20}-1$），初始时每个位置都存放着 $-1$（表示空位）。现在强哥需要处理 $Q$ 个操作请求，每个请求可能是以下两种类型之一：

1. 存入操作（$t_i=1$）：

   • 给定一个数字 $x_i$，需要找到一个空位存放它
   • 从 $h = x_i$ 开始，检查位置 $h \mod N$
   • 如果该位置不为空（不是 $-1$），就继续检查下一个位置（$h+1$）
   • 直到找到空位，将 $x_i$ 存入该位置

2. 查询操作（$t_i=2$）：

   • 给定一个数字 $x_i$，查询位置 $x_i \mod N$ 存放的数字
   • 直接输出该位置的值（可能是 $-1$）

数据范围

• $1 \leq Q \leq 2 \times 10^5$
• $t_i \in { 1, 2 \\} , (1 \leq i \leq Q)$
• $0 \leq x_i \leq 10^{18} , (1 \leq i \leq Q)$
• $t_i = 2$ 这样至少有 $i , (1 \leq i \leq Q)$ $1$ 个。
• 所有输入均为整数。

输入格式

Q
t₁ x₁
t₂ x₂
...
t_Q x_Q

输出格式

对于每个查询操作，输出一行结果

输入样例1

4
1 1048577
1 1
2 2097153
2 3

输出样例1

1048577
-1