Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

B. Minimize Equal Sum Subarrays
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
It is known that Farmer John likes Permutations, but I like them too!
— Sun Tzu, The Art of Constructing Permutations

You are given a permutation p of length n.

Find a permutation q of length n that minimizes the number of pairs (i,j) (1ijn) such that pi+pi+1++pj=qi+qi+1++qj.

A permutation of length n is an array consisting of n distinct integers from 1 to n in arbitrary order. For example, [2,3,1,5,4] is a permutation, but [1,2,2] is not a permutation (2 appears twice in the array), and [1,3,4] is also not a permutation (n=3 but there is 4 in the array).

Input

The first line contains t (1t104) — the number of test cases.

The first line of each test case contains n (1n2105).

The following line contains n space-separated integers p1,p2,,pn (1pin) — denoting the permutation p of length n.

It is guaranteed that the sum of n over all test cases does not exceed 2105.

Output

For each test case, output one line containing any permutation of length n (the permutation q) such that q minimizes the number of pairs.

Example
Input
3
2
1 2
5
1 2 3 4 5
7
4 7 5 1 2 6 3
Output
2 1
3 5 4 2 1
6 2 1 4 7 3 5
Note

For the first test, there exists only one pair (i,j) (1ijn) such that pi+pi+1++pj=qi+qi+1++qj, which is (1,2). It can be proven that no such q exists for which there are no pairs.