Куро играет в обучающую игру про числа. Основные математические операции в этой игре — наибольший общий делитель, побитовое исключающее ИЛИ и сумма двух чисел. Куро так любит эту игру, что проходит уровень за уровнем изо дня в день.
К сожалению, Куро уезжает в отпуск и будет неспособна продолжить череду решений. Поскольку Кэти — надёжный человек, Куро попросил её прийти к нему домой в этот день и поиграть за него.
Изначально дан пустой массив \(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, если таких чисел в массиве нет.
Поскольку вы программист, Кэти просит вас написать программу, которая будет автоматически и точно выполнять внутриигровые запросы, чтобы выполнить поручения Куро. Давайте поможем ей!
Выходные данные
Для каждого запроса типа \(2\) выведите запрашиваемое число \(v\) или -1, если таких чисел не найдено, в отдельной строке.