2108B.md (1835B)
1 Source: https://codeforces.com/problemset/problem/2108/B 2 3 B. SUMdamental Decomposition 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 On a recent birthday, your best friend Maurice gave you a pair of numbers $n$ and $x$, and asked you to construct an array of positive numbers $a$ of length $n$ such that $a_1 \oplus a_2 \oplus \cdots \oplus a_n = x$ $^{\text{∗}}$. 22 23 This task seemed too simple to you, and therefore you decided to give Maurice a return gift by constructing an array among all such arrays that has the smallest sum of its elements. You immediately thought of a suitable array; however, since writing it down turned out to be too time-consuming, Maurice will have to settle for just the sum of its elements. 24 25 $^{\text{∗}}$$\oplus$ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR). 26 27 Input 28 29 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. 30 31 Each test case consists of a single line containing a pair of numbers $n$ and $x$ ($1 \le n \le 10^9, \; 0 \le x \le 10^9$) — the numbers given to you by Maurice. 32 33 Output 34 35 For each test case, output your gift to Maurice — the sum of the elements of the array that satisfies all the described properties. If a suitable array does not exist, output $-1$. 36 37 Example 38 39 Input 40 41 ``` 42 8 43 44 2 1 45 46 3 6 47 48 1 0 49 50 2 0 51 52 5 0 53 54 2 27 55 56 15 43 57 58 12345678 9101112 59 ``` 60 61 Output 62 63 ``` 64 5 65 8 66 -1 67 2 68 8 69 27 70 55 71 21446778 72 ``` 73 74 Note 75 76 In the first test case, one of the suitable arrays is $[2, 3]$. It can be shown that it is impossible to achieve a smaller sum of array elements. 77 78 In the second case, one of the suitable arrays is $[1, 3, 4]$. It can also be shown that this is the optimal amount.