CF979D Kuro and GCD and XOR and SUM

Kuro 正在玩一个关于数字的益智游戏。这个游戏主要涉及最大公约数（GCD）、异或值（XOR）以及两个数的和。Kuro 非常喜欢这个游戏，每天都在一关一关地解题。 可惜的是，他要去度假一天，无法继续保持自己的解题连胜。由于 Katie 是个可靠的人，Kuro 特地请她在这一天到他家帮他玩这个游戏。 一开始，数组 $a$ 是空的。游戏包含 $q$ 个任务，分为两种类型。第一种类型要求 Katie 向 $a$ 中添加一个数 $u_i$。第二种类型要求 Katie 在 $a$ 中找到一个数 $v$，满足 $k_i \mid GCD(x_i, v)$，$x_i + v \leq s_i$，并且 $x_i \oplus v$ 最大，其中 $\oplus$ 表示[按位异或运算](https://en.wikipedia.org/wiki/Bitwise_operation#XOR)，$GCD(c, d)$ 表示整数 $c$ 和 $d$ 的[最大公约数](https://en.wikipedia.org/wiki/Greatest_common_divisor)，$y \mid x$ 表示 $x$ 能被 $y$ 整除。如果没有符合条件的数，则输出 $-1$。 由于你是程序员，Katie 需要你自动且准确地完成游戏中的任务，以满足她亲爱的朋友 Kuro。让我们来帮助她吧！

第一行包含一个整数 $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}$），你需要在数组 $a$ 中找到一个数 $v$，满足 $k_i \mid GCD(x_i, v)$，$x_i + v \leq s_i$，并且 $x_i \oplus v$ 最大，或者如果没有这样的数则输出 $-1$。 保证第一个任务类型为 $1$，且至少存在一个类型为 $2$ 的任务。

对于每个类型为 $2$ 的任务，输出一行，表示所需的数 $v$，如果没有符合条件的数则输出 $-1$。

在第一个样例中，有 5 个任务： - 第一个任务要求你将 $1$ 加入 $a$。此时 $a = \{1\}$。 - 第二个任务要求你将 $2$ 加入 $a$。此时 $a = \{1, 2\}$。 - 第三个任务询问 $x = 1$，$k = 1$，$s = 3$。$v$ 取 $1$ 和 $2$ 都满足 $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$。 由 ChatGPT 4.1 翻译