Kuro and GCD and XOR and SUM

Kuro는 현재 수에 관한 교육용 게임을 하고 있다. 이 게임은 최대공약수(GCD), XOR 값, 그리고 두 수의 합을 다룬다. Kuro는 이 게임을 매우 좋아해서 날마다 단계들을 차례로 푼다.

안타깝게도 그는 s 하루 동안 휴가를 떠나기 때문에 스스로 연속 풀이 기록을 이어 갈 수 없다. As Katie은 믿을 만한 사람이므로, Kuro는 이날 자신의 집에 와서 대신 게임을 해 달라고 그녀에게 정중히 부탁했다.

처음에는 빈 배열 a가 있다. 게임은 두 가지 유형의 q개 과제로 구성된다. 첫 번째 유형은 Katie에게 수 $u_i$를 a에 추가하라고 한다. 두 번째 유형은 a에 존재하는 수 v 중 $k_i$ ∣ GCD($x_i$, v), $x_i$ + v ≤ $s_i$를 만족하며 $x_i$ ⊕ v가 최대가 되는 수를 찾으라고 한다. 여기서 ⊕는 비트 단위 XOR 연산,을 나타내고, GCD(c, d)는 정수 c와 d의 최대공약수를 나타내며, y ∣ x는 x가 y로 나누어떨어진다는 뜻이다. 그러한 수를 찾을 수 없다면 -1을 보고한다.

당신은 프로그래머이므로, Katie가 소중한 친구 Kuro를 만족시킬 수 있도록 게임의 과제를 자동으로 정확하게 수행해 주어야 한다. 그녀를 도와주자s!

첫 번째 줄에 게임에서 수행해야 하는 과제의 수를 나타내는 하나의 정수 q (2 ≤ q ≤ $10^{5}$)가 주어진다.

이어서 q개의 줄이 주어지며, 각 줄은 과제의 유형을 나타내는 정수 $t_i$으로 시작한다:

• $t_i$ = 1이면, 정수 $u_i$가 (1 ≤ $u_i$ ≤ $10^{5}$) 뒤에 주어진다. $u_i$를 배열 a에 추가해야 한다.
• $t_i$ = 2이면, 세 정수 $x_i$, $k_i$, $s_i$가 (1 ≤ $x_i$, $k_i$, $s_i$ ≤ $10^{5}$) 뒤에 주어진다. 배열 a에 존재하는 수 v 중 $k_i$ ∣ GCD($x_i$, v), $x_i$ + v ≤ $s_i$를 만족하며 $x_i$ ⊕ v가 최대가 되는 수를 찾아야 한다. 여기서 ⊕는 XOR 연산을 나타낸다. 그러한 수를 찾을 수 없다면 -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 ∣ GCD(1, v) 및 1 + v ≤ 3을 만족한다. 2 ⊕ 1 = 3 > 1 ⊕ 1 = 0이므로, 이 과제의 답은 2이다.
• 네 번째 과제는 x = 1, k = 1, s = 2인 질문이다. v = 1만 1 ∣ GCD(1, v) 및 1 + v ≤ 2를 만족하므로, 이 과제의 답은 1이다.
• 다섯 번째 과제는 x = 1, k = 1, s = 1인 질문이다. 조건을 만족하는 a의 원소가 없으므로, 이 과제의 답으로 -1을 보고한다.