C. 67-я задача на перестановки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Придя в школу, Macaque был довольно грубо встречен его другом AG-88301, который не сделал домашнее задание, потому что всю ночь болтал с ничего не подозревающим незнакомцем о своей революционной работе над доказательством гипотезы Коллатца и о своей $$$67$$$-й безответной любви. Поэтому, как уже вошло в привычку, AG-88301, испытывая всё меньше благодарности и признательности, заставил Macaque сделать за него домашнее задание. В этот момент Macaque это окончательно надоело, и он обратился к своим миньонам (то есть к вам!), чтобы решить задачу AG-88301.

Вам дано целое число $$$n$$$. Необходимо построить перестановку$$$^{\text{∗}}$$$ длины $$$3n$$$ такую, что, если разбить эту перестановку на $$$n$$$ подряд идущих блоков по $$$3$$$ элемента, то сумма медиан$$$^{\text{†}}$$$ этих блоков будет максимальной.

Формально, требуется построить перестановку $$$p$$$ длины $$$3n$$$ такую, что $$$\sum_{i=0}^{n-1}\operatorname{median}(a_{3i+1},a_{3i+2},a_{3i+3})$$$ максимальна. Если существует несколько подходящих перестановок $$$p$$$, вы можете вывести любую из них.

$$$^{\text{∗}}$$$Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).

$$$^{\text{†}}$$$Медиана массива $$$b$$$, содержащего $$$3$$$ элемента, — это $$$2$$$-й элемент после сортировки $$$b$$$ в неубывающем порядке.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$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$$$.