← 返回题目列表

Codeforces · 1338/C

C. 完美三重奏

中文机器翻译题面 查看原题

考虑正整数的无限序列 $$$s$$$,通过重复以下步骤创建:

1. 找到按字典顺序最小的正整数三元组 $$$(a, b, c)$$$,使得 $$$a \oplus b \oplus c = 0$$$,其中 $$$\oplus$$$ 表示按位异或运算。 $$$a$$$、$$$b$$$、$$$c$$$ 不在$$$s$$$ 中。 这里,如果序列 $$$[a_1, b_1, c_1]$$$ 按字典顺序小于序列 $$$[a_2, b_2, c_2]$$$,则整数三元组 $$$(a_1, b_1, c_1)$$$ 被认为按字典顺序小于三元组 $$$(a_2, b_2, c_2)$$$。
2. 按此顺序将 $$$a$$$、$$$b$$$、$$$c$$$ 附加到 $$$s$$$。
3. 返回第一步。

您有整数 $$$n$$$。查找$$$s$$$ 中的第$$$n$$$ 个元素。

您必须回答 $$$t$$$ 独立测试用例。

如果在 $$$a$$$ 和 $$$b$$$ 不同的第一个位置,序列 $$$a$$$ 的元素比 $$$b$$$ 中的相应元素小,则序列 $$$a$$$ 按字典顺序小于序列 $$$b$$$。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^5$$$) — 测试用例的数量。

接下来的 $$$t$$$ 行都包含一个整数 $$$n$$$ ($$$1\le n \le 10^{16}$$$) — 您想知道的元素的位置。

输出

在每一 $$$t$$$ 行中,输出相应测试用例的答案。

示例

输入 #1

9
1
2
3
4
5
6
7
8
9

输出 #1

1
2
3
4
8
12
5
10
15

注意

$$$s$$$ 的第一个元素是 $$$1, 2, 3, 4, 8, 12, 5, 10, 15, \dots $$$