| The 2026 ICPC Belarus Qualification |
|---|
| Finished |
A dark magic shop has received the newest numeric tape made of antimatter. The tape is infinite in one direction and consists of cells with non-negative integers written on them: the number $$$0$$$ is written at the finite end, then the numbers $$$1$$$, $$$2$$$, $$$3$$$, $$$\ldots$$$, and so on to infinity.
For his research, Svetozar urgently needs a contiguous segment $$$[L, R]$$$ of this tape, and not just any segment, but one such that the bitwise XOR of all its numbers equals a given magic number $$$A$$$.
Magical goods are not cheap, so he needs a suitable segment with the smallest possible $$$R$$$. You may find any valid value of $$$L$$$. Anyway, when buying, the tape still has to be cut up to $$$R$$$ inclusive.
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^5$$$): the number of test cases. Then, $$$t$$$ test cases follow.
The only line of a test case contains an integer $$$A$$$ ($$$0 \leq A \leq 10^{18}$$$).
For each test case, print integers $$$L$$$ and $$$R$$$ ($$$0 \leq L \leq R \leq 10^{18}$$$) on a separate line: the bounds of a suitable segment. $$$R$$$ must be as small as possible. If there are several valid values of $$$L$$$ for the smallest $$$R$$$, print any.
It can be shown that under the given constraints at least one solution exists.
801234567
0 01 12 21 21 42 46 63 4
Recall that the bitwise XOR of two non-negative integers $$$x$$$ and $$$y$$$ is a non-negative integer $$$z$$$ whose binary representation has a bit equal to $$$1$$$ if the corresponding bits of $$$x$$$ and $$$y$$$ differ, and $$$0$$$ if they coincide.
| Name |
|---|


