← 返回题目列表

Codeforces · 1816/B

B. 电网重建

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

考虑一个 $$$2 \times n$$$ 网格,其中 $$$n$$$ 是偶数。您可以将整数 $$$1, 2, \ldots, 2n$$$ 放置在网格上,每个整数仅使用一次。

路径是通过从 $$$(1, 1)$$$ 开始,然后重复向下或向右行走,并在到达 $$$(2, n)$$$ 时停止而实现的单元序列。路径不应超出网格。

路径的成本是路径中单元格上写入的数字的交替总和。也就是说,让写在单元格上的数字为$$$a_1,a_2,\ldots,a_k$$$(按照访问的顺序),路径的成本为$$$a_1 - a_2 + a_3 - a_4 + \ldots = \sum_{i=1}^k a_i \cdot (-1)^{i+1}$$$。

构造一种方法,将整数 $$$1, 2, \ldots, 2n$$$ 放置在网格上,使得从 $$$(1, 1)$$$ 到 $$$(2, n)$$$ 的所有路径的最小成本最大化。如果有多个这样的网格导致最大值,则输出其中任何一个。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行也是唯一一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 10^5$$$, $$$n$$$ 是偶数) — 网格中的列数。

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

输出

对于每个测试用例,输出 $$$2$$$ 行,每行包含 $$$n$$$ 整数 - 所需的网格。如果有多个解,输出任意一个。

示例

输入 #1

3
2
4
6

输出 #1

3 2
1 4
8 2 6 4
1 5 3 7
11 5 9 1 7 3
6 10 2 8 4 12

注意

在第一个测试用例中,从单元格 $$$(1, 1)$$$ 到单元格 $$$(2, 2)$$$ 只有两条路径。他们的成本是 $$$3-1+4=6$$$ 和 $$$3-2+4=5$$$。那么最小成本是 $$$5$$$,这是最大可能值。

在第二个测试用例中,从单元格 $$$(1, 1)$$$ 到单元格 $$$(2, 4)$$$ 有四个路径。它们的成本为 $$$8-1+5-3+7=16$$$、$$$8-2+5-3+7=15$$$、$$$8-2+6-3+7=16$$$ 和 $$$8-2+6-4+7=15$$$。那么最小值是 $$$15$$$,这是可能的最大值。