Power Permutation - Repovive Premier Round 5 | Repovive

13A. Power Permutation

500 pts1s256 MB

You are given an integer $n$ .

Your task is to construct a permutation $p_1, p_2, \ldots, p_n$ of the numbers $1, 2, \ldots, n$ such that for every $i$ with $1 \le i \le n$ , the value $|i - p_i|$ is a power of two.

The number $0$ is not considered a power of two.

It is guaranteed that for every test case satisfying the constraints, at least one valid permutation exists.

Constraints

$1 \le t \le 10^5$
$2 \le n \le 2 \times 10^5$
The sum of $n$ over all test cases is at most $2 \times 10^5$

Input

t

\left. \begin{array}{l} n \end{array} \right\} \times t

Output

\left. \begin{array}{l} p_1 \quad p_2 \quad \cdots \quad p_n \end{array} \right\} \times t

For each test case, the printed sequence must be a valid permutation of the numbers $1, 2, \ldots, n$ .

If there are multiple valid answers, you may print any of them.

Samples

Input

Case 1

Case 2

Case 3

Case 4

Explanation

Case 1

For $i = 1$ , $|1 - 2| = 1$ . For $i = 2$ , $|2 - 1| = 1$ . All obtained values are powers of two.

Case 2

For $i = 1$ , $|1 - 2| = 1$ . For $i = 2$ , $|2 - 3| = 1$ . For $i = 3$ , $|3 - 1| = 2$ . All obtained values are powers of two.

Case 3

For $i = 1$ , $|1 - 2| = 1$ . For $i = 2$ , $|2 - 1| = 1$ . For $i = 3$ , $|3 - 4| = 1$ . For $i = 4$ , $|4 - 3| = 1$ . All obtained values are powers of two.

Case 4

For $i = 1$ , $|1 - 2| = 1$ . For $i = 2$ , $|2 - 3| = 1$ . For $i = 3$ , $|3 - 1| = 2$ . For $i = 4$ , $|4 - 5| = 1$ . For $i = 5$ , $|5 - 4| = 1$ . All obtained values are powers of two.

Output

Case 1

2 1

Case 2

2 3 1

Case 3

2 1 4 3

Case 4

2 3 1 5 4

You are given an integer $n$ .

Your task is to construct a permutation $p_1, p_2, \ldots, p_n$ of the numbers $1, 2, \ldots, n$ such that for every $i$ with $1 \le i \le n$ , the value $|i - p_i|$ is a power of two.

The number $0$ is not considered a power of two.

It is guaranteed that for every test case satisfying the constraints, at least one valid permutation exists.

$1 \le t \le 10^5$
$2 \le n \le 2 \times 10^5$
The sum of $n$ over all test cases is at most $2 \times 10^5$

t

\left. \begin{array}{l} n \end{array} \right\} \times t

\left. \begin{array}{l} p_1 \quad p_2 \quad \cdots \quad p_n \end{array} \right\} \times t

For each test case, the printed sequence must be a valid permutation of the numbers $1, 2, \ldots, n$ .

If there are multiple valid answers, you may print any of them.

For $i = 1$ , $|1 - 2| = 1$ . For $i = 2$ , $|2 - 1| = 1$ . All obtained values are powers of two.

For $i = 1$ , $|1 - 2| = 1$ . For $i = 2$ , $|2 - 3| = 1$ . For $i = 3$ , $|3 - 1| = 2$ . All obtained values are powers of two.

For $i = 1$ , $|1 - 2| = 1$ . For $i = 2$ , $|2 - 1| = 1$ . For $i = 3$ , $|3 - 4| = 1$ . For $i = 4$ , $|4 - 3| = 1$ . All obtained values are powers of two.

For $i = 1$ , $|1 - 2| = 1$ . For $i = 2$ , $|2 - 3| = 1$ . For $i = 3$ , $|3 - 1| = 2$ . For $i = 4$ , $|4 - 5| = 1$ . For $i = 5$ , $|5 - 4| = 1$ . All obtained values are powers of two.

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

13A. Power Permutation

Constraints

Input

Output

Samples

13A. Power Permutation

Constraints

Input

Output

Samples