Perfect Triples

Consider the infinite sequence $s$ of positive integers, created by repeating the following steps:

1. 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]$.
2. Append $a$, $b$, $c$ to $s$ in this order.
3. 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;
}