J. Антиматерия
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

В магазин товаров тёмной магии привезли новейшую числовую ленту из антиматерии. Лента бесконечна с одной стороны и состоит из клеток, на которых написаны целые неотрицательные числа: в конце написано число $$$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$$$ несколько, выведите любое.

Можно показать, что при заданных ограничениях хотя бы одно решение существует.

Пример
Входные данные
8
0
1
2
3
4
5
6
7
Выходные данные
0 0
1 1
2 2
1 2
1 4
2 4
6 6
3 4
Примечание

Напомним: побитовое исключающее ИЛИ (XOR) двух целых неотрицательных чисел $$$x$$$ и $$$y$$$ — это такое целое неотрицательное число $$$z$$$, в двоичном представлении которого бит равен $$$1$$$, если значения соответствующего бита чисел $$$x$$$ и $$$y$$$ различаются, или $$$0$$$, если совпадают.