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.

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

13A. Power Permutation

Constraints

Input

Output

Samples

13A. Power Permutation

Constraints

Input

Output

Samples