Kuro 目前正在玩一个关于数字的教育游戏。游戏重点关注最大公约数 (GCD)、XOR 值以及两个数字的和。 Kuro 非常喜欢这个游戏,他每天都会解决一个又一个的问题。
遗憾的是,他要去度假一天,他无法独自继续他的解决连续性。由于凯蒂是一个可靠的人,库洛好心地邀请她在这一天到他家来给他玩游戏。
最初,有一个空数组 $$$a$$$。游戏由两种类型的 $$$q$$$ 任务组成。第一种类型要求 Katie 将数字 $$$u_i$$$ 添加到 $$$a$$$。第二种类型要求 Katie 找到 $$$a$$$ 中存在的数字 $$$v$$$,使得 $$$k_i \mid GCD(x_i, v)$$$、$$$x_i + v \leq s_i$$$ 以及 $$$x_i \oplus v$$$ 最大化,其中 $$$\oplus$$$ 表示按位异或运算,$$$GCD(c, d)$$$ 表示整数 $$$c$$$ 和 $$$d$$$ 的最大公约数,$$$y \mid x$$$ 表示 $$$x$$$ 可以被 $$$y$$$ 整除,如果没有找到这样的数字则报告 -1。
由于你是一名程序员,凯蒂需要你自动准确地执行游戏中的任务来满足她亲爱的朋友库洛。我们来帮助她吧!
输入
第一行包含一个整数 $$$q$$$ ($$$2 \leq q \leq 10^{5}$$$) — 游戏希望你执行的任务数。
$$$q$$$ 行如下,每行以整数 $$$t_i$$$ 开头 - 任务的类型:
- 如果 $$$t_i = 1$$$,则后面跟着一个整数 $$$u_i$$$ ($$$1 \leq u_i \leq 10^{5}$$$) — 您必须将 $$$u_i$$$ 添加到数组 $$$a$$$ 中。
- 如果 $$$t_i = 2$$$,则后面跟着三个整数 $$$x_i$$$、$$$k_i$$$ 和 $$$s_i$$$ ($$$1 \leq x_i, k_i, s_i \leq 10^{5}$$$) — 您必须找到数组中存在的数字 $$$v$$$ $$$a$$$ 使得 $$$k_i \mid GCD(x_i, v)$$$、$$$x_i + v \leq s_i$$$ 和 $$$x_i \oplus v$$$ 最大化,其中 $$$\oplus$$$ 表示 XOR 运算,如果没有找到这样的数字则报告 -1。
保证第一个任务的类型为$$$1$$$类型,并且至少存在一个$$$2$$$类型的任务。
输出
对于 $$$2$$$ 类型的每个任务,在一行上输出所需的数字 $$$v$$$,如果未找到此类数字,则输出 -1。
示例
输入 #1
5 1 1 1 2 2 1 1 3 2 1 1 2 2 1 1 1
输出 #1
2 1 -1
输入 #2
10 1 9 2 9 9 22 2 3 3 18 1 25 2 9 9 20 2 25 25 14 1 20 2 26 26 3 1 14 2 20 20 9
输出 #2
9 9 9 -1 -1 -1
注意
在第一个示例中,有 5 个任务:
- 第一个任务要求您将 $$$1$$$ 添加到 $$$a$$$ 中。 $$$a$$$ 现在是 $$$\left\{1\right\}$$$。
- 第二个任务要求您将 $$$2$$$ 添加到 $$$a$$$ 中。 $$$a$$$ 现在是 $$$\left\{1, 2\right\}$$$。
- 第三个任务问你一个 $$$x = 1$$$、$$$k = 1$$$ 和 $$$s = 3$$$ 的问题。将 $$$1$$$ 和 $$$2$$$ 都视为 $$$v$$$ 满足 $$$1 \mid GCD(1, v)$$$ 和 $$$1 + v \leq 3$$$。因为 $$$2 \oplus 1 = 3 > 1 \oplus 1 = 0$$$,$$$2$$$ 是此任务的答案。
- 第四个任务问您一个问题,其中 $$$x = 1$$$、$$$k = 1$$$ 和 $$$s = 2$$$。只有 $$$v = 1$$$ 满足 $$$1 \mid GCD(1, v)$$$ 和 $$$1 + v \leq 2$$$,因此 $$$1$$$ 是此任务的答案。
- 第五个任务问您一个问题,其中 $$$x = 1$$$、$$$k = 1$$$ 和 $$$s = 1$$$。 $$$a$$$ 中没有满足条件的元素,因此我们报告 -1 作为此任务的答案。