YouKn0wWho has an integer sequence . He will perform the following operation until the sequence becomes empty: Select a non-empty subsequence of such that the bitwise XOR of the elements of the subsequence is , and then erase the elements of that subsequence.
He is wondering if it is possible to erase the whole sequence by performing the operation as many times as he wants. If possible, then he wants to find the minimum number of operations that he has to perform to erase the whole sequence. Help YouKn0wWho solve the problem as he is busy preparing a contest.
You will be given queries each containing an integer . Solve the problem independently for each .
The first line contains two space-separated integers and ().
The second line contains space-separated integers ().
Each of the following lines contains an integer ().
For each query -
Print -1, if it is not possible to erase the whole sequence by performing the aforementioned operation one or more times.
Otherwise, output the minimum number of operations that YouKn0wWho has to perform to erase the whole sequence.
Input | Output |
---|---|
5 5 1 3 2 5 5 7 10 3 0 8 | 2 -1 2 1 -1 |
In the first query, in the first operation erase the subsequence as . So the modified sequence will be . Now erase the whole sequence as . It can be shown that it is not possible erase the whole sequence using less than operations.
In the second query, it is not possible to erase the whole sequence.