Codeforces Round 865 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

constructive algorithms

greedy

*1000

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. Grid Reconstruction

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputConsider a $$$2 \times n$$$ grid, where $$$n$$$ is an even integer. You may place the integers $$$1, 2, \ldots, 2n$$$ on the grid, using each integer exactly once.

A path is a sequence of cells achieved by starting at $$$(1, 1)$$$, then repeatedly walking either downwards or to the right, and stopping when $$$(2, n)$$$ is reached. The path should not extend beyond the grid.

The cost of a path is the alternating sum of the numbers written on the cells in a path. That is, let the numbers written on the cells be $$$a_1, a_2, \ldots, a_k$$$ (in the order that it is visited), the cost of the path is $$$a_1 - a_2 + a_3 - a_4 + \ldots = \sum_{i=1}^k a_i \cdot (-1)^{i+1}$$$.

Construct a way to place the integers $$$1, 2, \ldots, 2n$$$ on the grid, such that the minimum cost over all paths from $$$(1, 1)$$$ to $$$(2, n)$$$ is maximized. If there are multiple such grids that result in the maximum value, output any of them.

Input

The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases. The description of test cases follows.

The first and the only line of each test case contains a single integer $$$n$$$ ($$$2 \leq n \leq 10^5$$$, $$$n$$$ is even) — the number of the columns in the grid.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output

For each test case, output $$$2$$$ lines, each containing $$$n$$$ integers — the desired grid. If there are multiple solutions, output any of them.

Example

Input

3246

Output

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

Note

In the first test case, there are only two paths from cell $$$(1, 1)$$$ to cell $$$(2, 2)$$$. Their costs are $$$3-1+4=6$$$ and $$$3-2+4=5$$$. Then the minimum cost is $$$5$$$, which is the maximum possible value.

In the second test case, there are four paths from cell $$$(1, 1)$$$ to cell $$$(2, 4)$$$. Their costs are $$$8-1+5-3+7=16$$$, $$$8-2+5-3+7=15$$$, $$$8-2+6-3+7=16$$$, and $$$8-2+6-4+7=15$$$. Then the minimum value is $$$15$$$, which is the maximum possible value.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/30/2023 20:36:52 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|