← 返回题目列表

Codeforces · 2175/B

B. 异或数组

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

给定三个整数 $$$n$$$、$$$l$$$ 和 $$$r$$$。

您需要生成一个长度为 $$$n$$$ 的正 ($$$1 \leq a_i \leq 10^9$$$) 整数数组 $$$a$$$。设 $$$f(x, y)$$$ 为 $$$1 \le x \le y \le n$$$ 的按位异或 $$$^{\text{*}}$$$ 值 $$$a_x \oplus a_{x+1} \oplus \ldots \oplus a_y$$$。您需要确保 $$\begin{cases} f(x, y) = 0\quad \text{当 }x = l\text{ 且 }y = r; \text{和}\\ f(x, y) \ne 0\quad \text{当 }x \ne l \text{ 或 } y \ne r 时。 \end{案例}$$

$$$^{\text{*}}$$$$$$\oplus$$$ 表示按位异或运算。

输入

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

每个测试用例的唯一行包含三个整数 $$$n$$$、$$$l$$$ 和 $$$r$$$ ($$$2 \leq n \leq 4\cdot 10^5$$$、$$$1 \leq l \lt r \leq n$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$5\cdot 10^5$$$。

输出

对于每个测试用例,打印一行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots a_n$$$。

我们可以证明答案总是存在的。如果有多个解决方案,请打印其中任何一个。

示例

输入
复制

4
3 1 3
4 1 3
8 2 4
4 3 4

输出
复制

9 8 1 
2 7 5 4 
9 1 9 8 10 5 4 9
85484 130377 6031 6031

注意

在第一个测试用例中, $$$f(1, 3) = 9 \oplus 8 \oplus 1 = 0$$$,而所有其他非空子数组都具有非零按位异或:

  • $$$f(1, 2) = 9 \oplus 8 = 1 \ne 0$$$,
  • $$$f(2, 3) = 8 \oplus 1 = 9 \ne 0$$$,
  • $$$f(1, 1) = 9 \ne 0$$$,
  • $$$f(2, 2) = 8 \ne 0$$$,
  • $$$f(3, 3) = 1 \ne 0$$$。

在第二个测试用例中,$$$2 \oplus 7 \oplus 5 = 0$$$,而例如$$$7 \oplus 5 \oplus 4 = 6 \ne 0$$$。