#GYM104745G. XOR + Constructive = Love
XOR + Constructive = Love
Description
Litusiano has, yet again, found another 8-pages-long statement. Disappointed with the problemsetters who create such long statements, he has created a problem with a very short statement. Now he has gifted it to you so that you can enjoy a short statement, for once. Unfortunately, Esomer is very evil and he has intercepted Litusiano's gift, adding this whole useless paragraph to annoy Litusiano.
You are given an array $a$ of length $30$ and you need to construct a new array $b$ of minimum length such that:
- There are at least $a_i$ elements with bit $i$ set in their binary representation, for $0 \le i < 30$.
- The sum of all the elements is $s$.
- The bitwise XOR$^\dagger$ of all the elements is exactly $x$.
If such an array doesn't exist, output $-1$ instead.
$^\dagger$If you don't know what bitwise XOR is, remember that you can use the internet!.
The first line of the input contains a single integer $t$, the number of test cases. ($1 \le t \le 10^4$).
On the first line of each test case there are two integers, $s$ and $x$, the required sum of all the elements in $b$ and the required XOR of all the elements in $b$, respectively. ($0 \le s \le 10^{18}$; $0 \le x < 2^{30}$).
Then comes a line with $30$ integers, $a_1, a_2, \ldots, a_{30}$, each $a_i$ denotes the minimum number all elements in $b$ that must have the $i$-th bit set on their binary representation. ($0 \le a_i \le 10^9$).
For each test case, if there doesn't exist any array that satisfies the conditions, print $-1$. Otherwise, print the minimum length of such an array.
Input
The first line of the input contains a single integer $t$, the number of test cases. ($1 \le t \le 10^4$).
On the first line of each test case there are two integers, $s$ and $x$, the required sum of all the elements in $b$ and the required XOR of all the elements in $b$, respectively. ($0 \le s \le 10^{18}$; $0 \le x < 2^{30}$).
Then comes a line with $30$ integers, $a_1, a_2, \ldots, a_{30}$, each $a_i$ denotes the minimum number all elements in $b$ that must have the $i$-th bit set on their binary representation. ($0 \le a_i \le 10^9$).
Output
For each test case, if there doesn't exist any array that satisfies the conditions, print $-1$. Otherwise, print the minimum length of such an array.
2
9 5
1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
9 6
1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3
9 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2147483648 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
104 10
5 2 3 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2
-1
2
-1
6
Note
—
Problem idea: Esomer
Problem preparation: Esomer
Ocurrences: Novice 7, Advanced 2