У Мари есть три целых числа \(n\), \(x\) и \(y\).
Назовем массив \(a\) из \(n\) неотрицательных целых чисел хорошим, если он удовлетворяет следующим ограничениям:
- \(a_1+a_2+\ldots+a_n=x\), и
- \(a_1 \, | \, a_2 \, | \, \ldots \, | \, a_n=y\), где \(|\) обозначает операцию побитового ИЛИ.
Значением хорошего массива называется значение \(a_1 \oplus a_2 \oplus \ldots \oplus a_n\), где \(\oplus\) обозначает операцию побитового исключающего ИЛИ.
Косия хочет, чтобы вы нашли побитовое исключающее ИЛИ значений всех хороших массивов. Если хороших массивов не существует, выведите \(0\).
Выходные данные
Выведите одно целое число — побитовое исключающее ИЛИ значений всех хороших массивов.
Примечание
В первом примере есть \(12\) хороших массивов, они перечислены ниже.
- \([0,2,3]\), \([0,3,2]\), \([2,0,3]\), \([2,3,0]\), \([3,0,2]\) и \([3,2,0]\): значение равно \(0 \oplus 2 \oplus 3 = 1\);
- \([1, 2, 2]\), \([2, 1, 2]\) and \([2, 2, 1]\): значение равно \(1 \oplus 2 \oplus 2 = 1\);
- \([1, 1, 3]\), \([1, 3, 1]\) and \([3, 1, 1]\): значение равно \(1 \oplus 1 \oplus 3 = 3\).
Поэтому побитовое исключющее ИЛИ значений всех хороших массивов равно \(\underbrace{1 \oplus \ldots \oplus 1}_{9\text{ раз}} \oplus 3 \oplus 3 \oplus 3 = 2\).
Во втором примере нет хороших массивов. Ответ должен быть \(0\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 5 3
|
2
|
|
2
|
100 0 100
|
0
|
|
3
|
79877974817 749875791743978 982783
|
64
|