2162C.md (1912B)
1 Source: https://codeforces.com/problemset/problem/2162/C 2 3 C. Beautiful XOR 4 5 time limit per test 6 7 2 seconds 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 You are given two integers $a$ and $b$. You are allowed to perform the following operation any number of times (including zero): 22 23 * choose any integer $x$ such that $0 \le x \le a$ (the current value of $a$, not initial), 24 * set $a := a \oplus x$. Here, $\oplus$ represents the [bitwise XOR](https://en.wikipedia.org/wiki/Bitwise_operation#XOR) operator. 25 26 After performing a sequence of operations, you want the value of $a$ to become exactly $b$. 27 28 Find a sequence of at most $100$ operations (values of $x$ used in each operation) that transforms $a$ into $b$, or report that it is impossible. 29 30 Note that you are not required to find the minimum number of operations, but any valid sequence of at most $100$ operations. 31 32 Input 33 34 The first line of input contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases. 35 36 Each test case contains two integers $a$ and $b$ ($1 \le a, b \le 10^9$). 37 38 Output 39 40 For each test case, if it is impossible to obtain $b$ from $a$ using the allowed operations, print a single line containing $-1$. 41 42 Otherwise, on the first line print a single integer $k$ ($0 \le k \le 100$) — the number of operations. On the second line print $k$ integers ($x_1, x_2, \dots , x_k$) — the chosen values of $x$ in the order you apply them. 43 44 If there are multiple valid sequences, you may print any one of them. 45 46 Example 47 48 Input 49 50 ``` 51 6 52 53 9 6 54 55 13 13 56 57 292 929 58 59 405 400 60 61 998 244 62 63 244 353 64 ``` 65 66 Output 67 68 ``` 69 2 70 71 7 8 72 73 0 74 75 -1 76 77 1 78 79 5 80 81 2 82 83 25 779 84 85 -1 86 ``` 87 88 Note 89 90 For the first test case, 91 92 * choose $x = 7$, now $a$ becomes equal to $9 \oplus 7 = 14$. 93 * choose $x = 8$, now $a$ becomes equal to $14 \oplus 8 = 6$. 94 95 Thus, we can make $a = b$. 96 97 For the fourth test case, choosing $x = 5$ makes $a = b$.