Hạo đang chơi trò chơi về những con số. Trò chơi chỉ có \(3\) phép toán đơn giản là tìm ước chung lớn nhất (GCD), tìm XOR và tìm tổng (SUM). Trò chơi sẽ nhiều yêu cầu, mỗi yêu cầu sẽ thực hiện một trong hai công việc sau:

• Loại \(1\) (\(1\) \(u\)): Thêm một số \(u\) vào mảng (mảng ban đầu rỗng)
• Loại \(2\) (\(2\) \(x\) \(k\) \(s\)): Tìm một số \(v\) trong mảng sao cho: \(GCD(x,v)\) \(\vdots\) \(k\) và \(SUM(x,v) \le s\) và \(x\) \(XOR\) \(v\) phải lớn nhất.

Hãy lập trình giúp Hạo có thể vượt qua được trò chơi này.

Dữ liệu vào

• Dòng đầu tiên: một số \(q\) \((2 \le q \le 10^5)\) - số lượng yêu cầu trong trò chơi.
• \(q\) dòng tiếp theo, mỗi dòng sẽ bắt đầu là một số nguyên \(t\) là loại công việc.
• Nếu \(t=1\) thì theo sau là số nguyên \(u\) \((1 \le u \le 10^5)\) là số bạn phải thêm vào mảng.
• Nếu \(t=2\) thì theo sau là \(3\) số \(x,k,s\) \((1 \le x,k,s \le 10^5)\): bạn phải tìm số \(v\) trong mảng thỏa mãn các điều kiện \(GCD(x,v)\) \(\vdots\) \(k\) và \(SUM(x,v) \le s\) và \(x \oplus v\) phải lớn nhất.
• Dữ liệu đảm bảo công việc đầu tiên luôn là loại \(1\) và có ít nhất một công việc loại \(2\)

Dữ liệu ra

• Ứng với mỗi công việc loại \(2\), bạn phải in ra số \(v\) nếu không tìm được thì in \(-1\)

Input 1

5
1 1
1 2
2 1 1 3
2 1 1 2
2 1 1 1

Output 1

2
1
-1

Input 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

Output 2

9
9
9
-1
-1
-1