← 返回题目列表

Codeforces · 979/D

D. Kuro 和 GCD 和 XOR 和 SUM

中文机器翻译题面 查看原题

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 作为此任务的答案。