You are given a sequence of integers of length $n$: $a_1, a_2, \dots, a_n$.

Consider all $n$ possible cyclic shifts (rotations) of this sequence. For a starting position $p$ ($1 \le p \le n$), the corresponding cyclic shift is the sequence

$$b_1, b_2, \dots, b_n = a_p, a_{p+1}, \dots, a_n, a_1, a_2, \dots, a_{p-1}.$$

For this shifted sequence, define its prefix maximum sequence $c_1, c_2, \dots, c_n$ by

$$c_i = \max(b_1, b_2, \dots, b_i) \quad \forall i = 1, 2, \dots, n.$$

We compare two sequences of the same length using the usual lexicographical order: $c$ is lexicographically smaller than $d$ if and only if there exists an index $i$ such that $c_1 = d_1, c_2 = d_2, \dots, c_{i-1} = d_{i-1}$ and $c_i < d_i$.

Your task is to choose a cyclic shift of the original sequence such that its prefix maximum sequence is lexicographically smallest among all $n$ possible cyclic shifts.

Input

The first line contains a single integer $T$ ($1 \le T \le 2 \cdot 10^5$), the number of test cases.

Each test case consists of two lines:

• The first line contains a single integer $n$ ($1 \le n \le 5 \cdot 10^5$).
• The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$).

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

Output

For each test case, output one line containing $n$ integers: the lexicographically smallest prefix maximum sequence after cyclic shift.

Example

6
5
5 4 3 2 1
4
1 3 1 3
5
1 2 1 3 1
5
2 3 2 1 1
6
1 2 1 3 1 4
6
2 1 3 1 4 1

1 5 5 5 5
1 3 3 3
1 1 2 2 3
1 1 2 3 3
1 2 2 3 3 4
1 2 2 3 3 4