← 返回题目列表

Codeforces · 2057/C

C. 奥林匹克之旅

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

明年会有很多团体奥运会,所以“T一代”的老师需要组建一个由三名学生组成的团队来参加。任何三名学生都将在任何团体奥林匹克竞赛中取得不错的成绩。但赢得奥运会只是成功的一半;首先,你需要到达那里......

每个学生都有一个独立水平,以整数表示。在“T一代”中,只有一名学生的独立程度从$$$l$$$到$$$r$$$(含)。对于独立程度为 $$$a$$$、$$$b$$$ 和 $$$c$$$ 的三名学生组成的团队,他们的团队独立性值等于 $$$(a \oplus b) + (b \oplus c) + (a \oplus c)$$$,其中 $$$\oplus$$$ 表示按位异或运算。

你的任务是选择具有最大可能团队独立性的任意三名学生。

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例集的第一行包含两个整数 $$$l$$$ 和 $$$r$$$ ($$$0 \le l, r < 2^{30}$$$, $$$r - l > 1$$$) - 学生的最小和最大独立水平。

输出

对于每个测试用例集,输出三个成对不同的整数 $$$a、b$$$ 和 $$$c$$$,使得 $$$l \le a, b, c \le r$$$ 并且表达式 $$$(a \oplus b) + (b \oplus c) + (a \oplus c)$$$ 的值最大化。如果存在多个具有最大值的三元组,则可以输出其中任何一个。

示例

输入 #1

8
0 2
0 8
1 3
6 22
128 137
69 98
115 127
0 1073741823

输出 #1

1 2 0
8 7 1
2 1 3
7 16 11
134 132 137
98 85 76
123 121 118
965321865 375544086 12551794

注意

在第一个测试用例中,唯一合适的数字三元组 ($$$a, b, c$$$)(最多排列)是 ($$$0, 1, 2$$$)。

在第二个测试用例中,合适的三元组之一是 ($$$8, 7, 1$$$),其中 $$$(8 \oplus 7) + (7 \oplus 1) + (8 \oplus 1) = 15 + 6 + 9 = 30$$$。可以证明,$$$30$$$ 是 $$$(a \oplus b) + (b \oplus c) + (a \oplus c)$$$ 对于 $$$0 \le a, b, c \le 8$$$ 的最大可能值。