Вам дано \(n\) объектов. У каждого объекта есть два целочисленных свойства: \(val_i\) — его цена — и \(mask_i\). Гарантируется, что изначально сумма цен всех объектов не равна нулю.
Вы хотите выбрать некоторое целое положительное число \(s\). После этого все объекты модифицируется, причем \(i\)-й объект модифицируется следующим образом:
- рассмотрим \(mask_i\) и \(s\) в двоичной системе счисления,
- вычислим побитовое «И» \(s\) и \(mask_i\) (\(s \,\&\, mask_i\)),
- если (\(s \,\&\, mask_i\)) содержит нечётное число единиц в двоичной записи, то \(val_i\) меняется на \(-val_i\). Иначе с \(i\)-м объектом ничего не происходит.
Нужно найти такое целое число \(s\), что если произвести модификацию, как описано выше, то сумма всех цен сменит знак (если она была отрицательной, то она должна стать положительной, и наоборот; не разрешается сумме становится нулём). При этом абсолютное значение суммы цен может стать любым.
Выходные данные
Выведите целое число \(s\) (\(1 \le s \le 2^{62} - 1\)) такое, что если его произвести модификацию, как описано выше, то сумма всех \(val_i\) сменит знак.
В случае если существует несколько таких \(s\), выведите любое из них. Можно показать, что всегда существует хотя бы одно подходящее \(s\).
Примечание
В первом тестовом примере все объекты изменят свою стоимость кроме объекта с маской \(151\).
Поэтому их сумма изменит знак: изначально \(24\), после модификаций — \(-28\).
Во втором тестовом примере единственный объект поменяет свою стоимость. Поэтому сумма всех цен изменит знак.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
17 206
-6 117
-2 151
9 93
6 117
|
64
|
|
2
|
1
1 1
|
1
|