Consider the infinite sequence $s$ of positive integers, created by repeating the following steps:
- Find the lexicographically smallest triple of positive integers $(a, b, c)$ such that
- $a \oplus b \oplus c = 0$, where $\oplus$ denotes the bitwise XOR operation.
- $a$, $b$, $c$ are not in $s$.Here triple of integers $(a_1, b_1, c_1)$ is considered to be lexicographically smaller than triple $(a_2, b_2, c_2)$ if sequence $[a_1, b_1, c_1]$ is lexicographically smaller than sequence $[a_2, b_2, c_2]$.
- Append $a$, $b$, $c$ to $s$ in this order.
- Go back to the first step.
You have integer $n$. Find the $n$-th element of $s$.
You have to answer $t$ independent test cases.
A sequence $a$ is lexicographically smaller than a sequence $b$ if in the first position where $a$ and $b$ differ, the sequence $a$ has a smaller element than the corresponding element in $b$.Input
The first line contains a single integer $t$ ($1 \le t \le 10^5$) — the number of test cases.
Each of the next $t$ lines contains a single integer $n$ ($1\le n \le 10^{16}$) — the position of the element you want to know.Output
In each of the $t$ lines, output the answer to the corresponding test case.
Example input
9 1 2 3 4 5 6 7 8 9
output
1 2 3 4 8 12 5 10 15
Note
The first elements of $s$ are $1, 2, 3, 4, 8, 12, 5, 10, 15, \dots $
Solution:
#include <bits/stdc++.h> using namespace std; pair<long long, long long> Get(int bit, long long idx) { if (bit == 0) { return make_pair(1, 2); } long long some = 1LL << (bit - 2); auto q = Get(bit - 2, idx % some); q.first ^= (1LL << (bit - 2)); q.second ^= (1LL << (bit - 1)); long long cs = idx / some; if (cs == 1) { q.first ^= (1LL << (bit - 2)); q.second ^= (1LL << (bit - 1)); } if (cs == 2) { q.first ^= (1LL << (bit - 1)); q.second ^= (1LL << (bit - 1)) ^ (1LL << (bit - 2)); } if (cs == 3) { q.first ^= (1LL << (bit - 1)) ^ (1LL << (bit - 2)); q.second ^= (1LL << (bit - 2)); } q.first ^= 1LL << bit; q.second ^= 1LL << (bit + 1); return q; } int main() { ios::sync_with_stdio(false); cin.tie(0); int tt; cin >> tt; while (tt--) { long long n; cin >> n; long long idx = (n - 1) / 3; long long pos = (n - 1) % 3; for (int bit = 0; ; bit += 2) { long long here = 1LL << bit; if (idx < here) { auto p = Get(bit, idx); cout << (pos == 0 ? p.first : (pos == 1 ? p.second : (p.first ^ p.second))) << '\n'; break; } idx -= here; } } return 0; }