Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

C. Битовый баланс
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Даны три неотрицательных целых числа $$$b$$$, $$$c$$$ и $$$d$$$.

Найдите неотрицательное целое число $$$a \in [0, 2^{61}]$$$, такое что $$$(a\, |\, b)-(a\, \&\, c)=d$$$, где $$$|$$$ и $$$\&$$$ обозначают операцию побитового ИЛИ и операцию побитового И соответственно.

Если такое $$$a$$$ существует, выведите его значение. Если решения не существует, выведите одно целое число $$$-1$$$. Если существует несколько решений, выведите любое из них.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^5$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Единственная строка каждого набора входных данных содержит три целых числа $$$b$$$, $$$c$$$ и $$$d$$$ ($$$0 \le b, c, d \le 10^{18}$$$).

Выходные данные

Для каждого набора входных данных выведите значение $$$a$$$ или $$$-1$$$, если решения не существует. Обратите внимание, что $$$a$$$ должно быть неотрицательным и не может превышать $$$2^{61}$$$.

Пример
Входные данные
3
2 2 2
4 2 6
10 2 14
Выходные данные
0
-1
12
Примечание

В первом наборе входных данных $$$(0\,|\,2)-(0\,\&\,2)=2-0=2$$$. Так что $$$a = 0$$$ является корректным ответом.

Во втором наборе входных данных никакое значение $$$a$$$ не удовлетворяет уравнению.

В третьем наборе входных данных $$$(12\,|\,10)-(12\,\&\,2)=14-0=14$$$. Так что $$$a = 12$$$ является корректным ответом.