| The 2026 ICPC Belarus Qualification |
|---|
| Закончено |
В магазин товаров тёмной магии привезли новейшую числовую ленту из антиматерии. Лента бесконечна с одной стороны и состоит из клеток, на которых написаны целые неотрицательные числа: в конце написано число $$$0$$$, затем числа $$$1$$$, $$$2$$$, $$$3$$$, $$$\ldots$$$, и так до бесконечности.
Светозару для его исследований позарез нужен непрерывный отрезок $$$[L, R]$$$ такой ленты, да не простой отрезок, а такой, что побитовое исключающее ИЛИ (XOR) всех его чисел в точности равно заданному волшебному числу $$$A$$$.
Магические товары стоят недёшево, поэтому ему требуется найти подходящий отрезок с минимальным $$$R$$$. Вы можете отыскать любое корректное значение $$$L$$$ — всё равно при покупке придётся отрезать кусок ленты до числа $$$R$$$ включительно.
Первая строка содержит целое число $$$t$$$ ($$$1 \leqslant t \leqslant 2 \cdot 10^5$$$) — количество тестовых случаев. Далее следуют $$$t$$$ описаний тестовых случаев.
Единственная строка описания содержит целое число $$$A$$$ ($$$0 \leqslant A \leqslant 10^{18}$$$).
Для каждого тестового случая выведите в отдельной строке два целых числа $$$L$$$ и $$$R$$$ ($$$0 \leqslant L \leqslant R \leqslant 10^{18}$$$) — границы подходящего отрезка. $$$R$$$ должно быть минимально возможным. Если при минимальном $$$R$$$ подходящих значений $$$L$$$ несколько, выведите любое.
Можно показать, что при заданных ограничениях хотя бы одно решение существует.
801234567
0 01 12 21 21 42 46 63 4
Напомним: побитовое исключающее ИЛИ (XOR) двух целых неотрицательных чисел $$$x$$$ и $$$y$$$ — это такое целое неотрицательное число $$$z$$$, в двоичном представлении которого бит равен $$$1$$$, если значения соответствующего бита чисел $$$x$$$ и $$$y$$$ различаются, или $$$0$$$, если совпадают.
| Название |
|---|


