D. Kuro and GCD and XOR and SUM

Kuro is currently playing an educational game about numbers. The game focuses on the greatest common divisor (GCD), the XOR value, and the sum of two numbers. Kuro loves the game so much that he solves levels by levels day by day.

Sadly, he's going on a vacation for a day, and he isn't able to continue his solving streak on his own. As Katie is a reliable person, Kuro kindly asked her to come to his house on this day to play the game for him.

Initally, there is an empty array -1 if no such numbers are found.

Since you are a programmer, Katie needs you to automatically and accurately perform the tasks in the game to satisfy her dear friend Kuro. Let's help her!

Input

The first line contains one integer 2≤q≤105) — the number of tasks the game wants you to perform.

ti — the type of the task:

If a.
If -1 if no such numbers are found.

It is guaranteed that the type of the first task is type 2.

Output

For each task of type -1 if no such numbers are found.

Examples

input

output

2
1
-1

input

output

9
9
9
-1
-1
-1

Note

In the first example, there are 5 tasks:

The first task requires you to add {1}.
The second task requires you to add {1,2}.
The third task asks you a question with 2 is the answer to this task.
The fourth task asks you a question with 1 is the answer to this task.
The fifth task asks you a question with -1 as the answer to this task.

这题其实可以说是01字典树的裸题，看了别人的题解然后就去学了一下01字典树

现在我也只是刚刚学有点懵逼

D. Kuro and GCD and XOR and SUM

我看这篇博客学的转载

源地址https://blog.****.net/riba2534/article/details/80344026

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #include<vector>
  5 #include<queue>
  6 #define inf 0x3fffffff
  7 
  8 using namespace std;
  9 typedef long long LL;
 10 const int maxn = 2e5 + 10;
 11 int a[maxn], minn[maxn], tree[32 * maxn][2];
 12 int sum, root;
 13 int newnode() {
 14     tree[sum][0] = tree[sum][1] = -1;
 15     sum++;
 16     return sum - 1;
 17 }
 18 
 19 void init() {
 20     sum = 0 ;
 21     memset(minn, 0x3f, sizeof(minn));
 22     root = newnode();
 23 }
 37 void add(int x) {
 38     int p = x;
 39     int now = root ;
 40     minn[now] = min(minn[now], p);
 41     for (int i = 31 ; i >= 0 ; i--) {
 42         int  to = (x >> i) & 1;
 43         if (tree[now][to] == -1)  tree[now][to] = newnode();
 44         now = tree[now][to];
 45         minn[now] = min(minn[now], p);
 46     }
 47 }
 48 /*
 49 int getans(int x, int p) {
 50     int now = root;
 51     if (minn[now] > p) return -1;
 52     for (int i = 31 ; i >= 0 ; i-- ) {
 53         int to = (x >> i) & 1 ;
 54         if (tree[now][to ^ 1] != -1 && minn[tree[now][to ^ 1]] <= p   ) to ^= 1;
 55         now = tree[now][to];
 56     }
 57     return minn[now];
 58 }*/
 59 int getans(int x, int p) {
 60     int now = root ;
 61     if (minn[now] > p ) return -1;
 62     for (int i = 31 ; i >= 0 ; i--  ) {
 63         int to = (x >> i) & 1;
 64         if (tree[now][to ^ 1] != -1 && minn[tree[now][to ^ 1]] <= p ) to ^= 1;
 65         now = tree[now][to];
 66     }
 67     return minn[now];
 68 }
 69 int main() {
 70     int t, op, x, k, s;
 71     init();
 72     scanf("%d", &t);
 73     while(t--) {
 74         scanf("%d", &op);
 75         if (op == 1) {
 76             scanf("%d", &x);
 77             a[x] = 1;
 78             add(x);
 79         } else {
 80             scanf("%d%d%d", &x, &k, &s);
 81             if (x % k != 0) {
 82                 printf("-1
");
 83                 continue;
 84             }
 85             if (k == 1) {
 86                 printf("%d
", getans(x, s - x));
 87                 continue;
 88             }
 89             int maxn = -1, ans = -1;
 90             for (int i = k ; i <= s - x ; i += k)  {
 91                 if (a[i] && (i ^ x) > maxn) {
 92                     maxn = i ^ x;
 93                     ans = i;
 94                 }
 95             }
 96             printf("%d
", ans);
 97         }
 98     }
 99     return 0;
100 }

相关推荐