D. Куро, НОД, побитовое исключающее ИЛИ, сумма и все-все-все
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Куро играет в обучающую игру про числа. Основные математические операции в этой игре — наибольший общий делитель, побитовое исключающее ИЛИ и сумма двух чисел. Куро так любит эту игру, что проходит уровень за уровнем изо дня в день.

К сожалению, Куро уезжает в отпуск и будет неспособна продолжить череду решений. Поскольку Кэти — надёжный человек, Куро попросил её прийти к нему домой в этот день и поиграть за него.

Изначально дан пустой массив $$$a$$$. Игр состоит из $$$q$$$ запросов двух разных типов. Запросы первого типа просят Кэти добавить число $$$u_i$$$ в массив $$$a$$$. Запросы второго типа просят Кэти найти такое число $$$v$$$, принадлежащее массиву $$$a$$$, что $$$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$$$ обозначает побитовое исключающее ИЛИ, или вывести -1, если таких чисел в массиве нет.

Гарантируется, что первый запрос имеет тип $$$1$$$ и что существует хотя бы один запрос типа $$$2$$$.

Выходные данные

Для каждого запроса типа $$$2$$$ выведите запрашиваемое число $$$v$$$ или -1, если таких чисел не найдено, в отдельной строке.

Примеры
Входные данные
5
1 1
1 2
2 1 1 3
2 1 1 2
2 1 1 1
Выходные данные
2
1
-1
Входные данные
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
Выходные данные
9
9
9
-1
-1
-1
Примечание

В первом примере необходимо выполнить пять запросов:

  • Первый запрос просит вас добавить $$$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 как ответ на этот запрос.