Совсем скоро у Ярика день рождения, и Марк решил подарить ему массив \(a\) длины \(n\).
Марк знает, что Ярик очень любит битовые операции, а также у него есть любимое число \(x\), поэтому Марк хочет найти такое максимальное число \(k\), что можно выбрать такие пары чисел [\(l_1, r_1\)], [\(l_2, r_2\)], \(\ldots\) [\(l_k, r_k\)], что:
- \(l_1 = 1\).
- \(r_k = n\).
- \(l_i \le r_i\) для всех \(i\) от \(1\) до \(k\).
- \(r_i + 1 = l_{i + 1}\) для всех \(i\) от \(1\) до \(k - 1\).
- \((a_{l_1} \oplus a_{l_1 + 1} \oplus \ldots \oplus a_{r_1}) | (a_{l_2} \oplus a_{l_2 + 1} \oplus \ldots \oplus a_{r_2}) | \ldots | (a_{l_k} \oplus a_{l_k + 1} \oplus \ldots \oplus a_{r_k}) \le x\), где \(\oplus\) обозначает операцию побитового исключающего ИЛИ, а \(|\) обозначает операцию побитового ИЛИ.
Если такого \(k\) не существует, то нужно вывести \(-1\).
Выходные данные
Для каждого набора входных данных в отдельной строке выведите одно целое число — максимальное подходящее число \(k\), и \(-1\), если такого \(k\) не существует.
Примечание
В первом наборе входных данных можно взять \(k\) равным \(2\) и выбрать два отрезка [\(1, 1\)] и [\(2, 3\)], \((1) | (2 \oplus 3) = 1\). Можно показать, что \(2\) — максимальный возможный ответ.
Во втором наборе входных данных подходят отрезки [\(1, 1\)] и [\(2, 2\)], \((1) | (1) = 1\). Больше отрезков сделать нельзя.
В третьем наборе входных данных нельзя выбрать \(2\) отрезка, так как \((1) | (3) = 3 > 2\), значит оптимальный ответ это \(1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8
3 1
1 2 3
2 2
1 1
2 2
1 3
2 3
0 0
3 2
0 0 1
4 2
1 3 3 7
2 2
2 3
5 0
0 1 2 2 1
|
2
2
1
2
3
-1
1
2
|