Вам даны три целых числа \(a\), \(b\), \(d\). Найдите целое число \(x\), удовлетворяющее следующим требованиям, или сообщите, что такого числа не существует:
- \(0 \le x \lt 2^{60}\);
- \(a|x\) делится на \(d\);
- \(b|x\) делится на \(d\).
Здесь \(|\) обозначает операцию побитового ИЛИ.
Выходные данные
Для каждого набора входных данных выведите одно число:
- если существует число \(x\), удовлетворяющее требованиям из условия, выведите \(x\);
- иначе, выведите \(-1\).
Если существует несколько решений, выведите любое из них.
Примечание
В первом наборе входных данных одно из возможных решений \(x=18\). Оно корректно, так как \(39|18=55\) и \(12|18=30\) делятся на \(d=5\).
Во втором наборе входных данных одно из возможных решений \(x=14\). Оно корректно, так как \(8|14=6|14=14\) делится на \(d=14\).
Можно показать, что в третьем и четвёртом наборах входных данных решений не существует.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8
12 39 5
6 8 14
100 200 200
3 4 6
2 2 2
18 27 3
420 666 69
987654321 123456789 999999999
|
18
14
-1
-1
0
11
25599
184470016815529983
|