题目描述

线性探查存储器是一种按照线性方式存储数据的结构。

它包含$n=2^{20}$个槽位，初始时每个槽位都存储$-1$，表示为空。

其储存方式为：如果你要将数$x$储存到其中，指针会找到$h = x \% n$的位置，如果位置$h$为空（$a[h] = -1$），就将$x$插入该位置，否则遇到冲突，指针跳到下一个位置，如果当前指针指向的位置已经是储存器的最后一个位置，指针就跳转到储存器的第一个位置，直到某一时刻指针指向的位置不为空，将$x$插入此位置。

现在你需要处理一些询问，每次询问有以下两种类型：

• 插入：将$x$插入到储存器中。
• 查询：查询当前位置$x\%n$上储存的数的值。

输入格式

第一行包含一个正整数$q(1\le q \le2 \times 10^5)$，询问的次数。

接下来$q$行，每行包含两个整数$t_i (t_i ∈\{1, 2\})$和$x_i(0 \le x_i \le 10^{18})$

• 如果$t_i = 1$表示插入操作
• 如果$t_i = 2$表示查询操作

输出格式

对于每个查询操作，输出一行一个整数，表示查询结果，如果当前位置为空，输出$-1$。

题目保证至少存在一个查询操作。

样例

4
1 1048577
1 1
2 2097153
2 3

1048577
-1