到达学校后,猕猴受到了他的朋友 AG-88301 的粗鲁欢迎,后者因为整晚都在向一个毫无戒心的陌生人大喊大叫,谈论他在证明 Collatz 猜想方面的开创性工作以及他第 67 美元的无回报的爱情兴趣,所以他放弃了家庭作业。因此,按照惯例,AG-88301以越来越低的感激或欣赏程度,让猕猴帮他做作业。此时,猕猴已经受够了,转向他的爪牙(你们这些家伙!)来解决 AG-88301 的作业任务。
给你一个整数$$$n$$$。您必须构建长度为 $$$3n$$$ 的排列$$$^{\text{∗}}$$$,这样,如果您将排列划分为包含 $$$3$$$ 元素的 $$$n$$$ 个连续块,则这些块的中位数 $$$^{\text{†}}$$$ 的总和为 最大化.
更正式地说,您必须构造一个长度为 $$$3n$$$ 的排列 $$$p$$$,使得 $$$\sum_{i=0}^{n-1}\operatorname{median}(a_{3i+1},a_{3i+2},a_{3i+3})$$$ 最大化。如果有多个可能的$$$p$$$,则输出任意一个。
$$$^{\text{*}}$$$长度$$$n$$$的排列是一个由从$$$1$$$到$$$n$$$以任意顺序的$$$n$$$个不同整数组成的数组。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。
$$$^{\text{†}}$$$包含$$$3$$$元素的数组$$$b$$$的中位数是$$$b$$$按非降序排序后的第$$$2$$$个元素。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行也是唯一一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^5$$$)。
保证所有测试用例的 $$$3n$$$ 之和不超过 $$$3 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个排列$$$p$$$,使得连续块的中位数之和最大化。如果有多个可能的$$$p$$$,则输出任意一个。
示例
输入复制
3 2 1 3
输出复制
1 3 4 2 5 6 3 1 2 5 2 4 8 3 9 7 1 6
注意
在第一个测试用例中, $$$[1,3,4,2,5,6]$$$ 是一个可能的答案,因为 $$$\operatorname{median}(1,3,4) + \operatorname{median}(2,5,6) = 3+5 = 8$$$,并且可以证明 $$$8$$$ 是中位数的最大可能总和。
在第二个测试用例中,$$$[3,1,2]$$$ 是一个可能的答案,因为当 $$$n=1$$$ 时唯一可实现的中位数总和是 $$$2$$$。