1775C.md (1784B)
1 Source: https://codeforces.com/problemset/problem/1775/C 2 3 C. Interesting Sequence 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Petya and his friend, robot Petya++, like to solve exciting math problems. 22 23 One day Petya++ came up with the numbers $n$ and $x$ and wrote the following equality on the board: $$n\ \&\ (n+1)\ \&\ \dots\ \&\ m = x,$$ where $\&$ denotes the [bitwise AND operation](https://en.wikipedia.org/wiki/Bitwise_operation#AND). Then he suggested his friend Petya find such a minimal $m$ ($m \ge n$) that the equality on the board holds. 24 25 Unfortunately, Petya couldn't solve this problem in his head and decided to ask for computer help. He quickly wrote a program and found the answer. 26 27 Can you solve this difficult problem? 28 29  30 31 Input 32 33 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 2000$). The description of the test cases follows. 34 35 The only line of each test case contains two integers $n$, $x$ ($0\le n, x \le 10^{18}$). 36 37 Output 38 39 For every test case, output the smallest possible value of $m$ such that equality holds. 40 41 If the equality does not hold for any $m$, print $-1$ instead. 42 43 We can show that if the required $m$ exists, it does not exceed $5 \cdot 10^{18}$. 44 45 Example 46 47 Input 48 49 ``` 50 5 51 52 10 8 53 54 10 10 55 56 10 42 57 58 20 16 59 60 1000000000000000000 0 61 ``` 62 63 Output 64 65 ``` 66 12 67 10 68 -1 69 24 70 1152921504606846976 71 ``` 72 73 Note 74 75 In the first example, $10\ \&\ 11 = 10$, but $10\ \&\ 11\ \&\ 12 = 8$, so the answer is $12$. 76 77 In the second example, $10 = 10$, so the answer is $10$. 78 79 In the third example, we can see that the required $m$ does not exist, so we have to print $-1$.