We have a strange box with a big red button. There is a sequence of integers in the box. Whenever we push the big red button, the sequence in the box changes. We call the box a “copier”, because the new sequence is created from the old one by copying some contiguous section.

More precisely, each time the red button is pushed the copier does the following: Suppose that the current sequence in the box is *a*_{0}, *a*_{1}, *a*_{2}, …, *a*_{m − 1}. The copier chooses some *i*, *j*, *k* such that 0 ≤ *i* < *j* ≤ *k* ≤ *m*. Then the copier inserts a copy of *a*_{i}, …, *a*_{j − 1} immediately after *a*_{k − 1}. Note that *j* ≤ *k*: the copy is always inserted to the right of the original. Here is how the sequence looks like after the insertion:

$$ a_0, \dots, a_{i-1}, \underbrace{a_i, \dots, a_{j-1}}_{\rm original}, a_j, \dots, a_{k-1}, \underbrace{a_i, \dots, a_{j-1}}_{\rm copy}, a_k, \dots, a_{m-1} $$

In the morning we had some **permutation** of 1…ℓ in the box. Then we pushed the button zero or more times. Each time we pushed the button, a new (not necessarily different) triple (*i*, *j*, *k*) was chosen and the sequence was modified as described above. You are given the sequence *S* that was in the copier at the end of the day. Reconstruct the original permutation.

The first line of the input file contains an integer *t* ≤ 60 specifying the number of test cases. Each test case is preceded by a blank line.

Each test case consists of two lines. The first line contains an integer *n* (3 ≤ *n* ≤ 100 000) – the length of the final sequence *S*. The second line contains *n* integers – the sequence *S*. For each test case, there is a positive integer ℓ such that *S* can be produced from some permutation of {1, 2, …, ℓ} using a finite sequence of copier operations.

In the **easy subproblem C1** you may also assume that *n* ≤ 10 000, that the sequence *S* was obtained from some permutation by pushing the red button exactly once, and that the copier chose *j* = *k*, i.e., it inserted the copied subsequence immediately after the original.

For each test case, output a single line with a space-separated list of integers: the original permutation. If there are multiple valid solutions, output any of them.

**Input:**

```
3
7
5 1 4 1 4 2 3
11
4 3 1 2 3 1 4 3 3 1 4
7
1 1 1 1 1 1 1
```

**Output:**

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

*The first test case satisfies the conditions for the easy subproblem, the copier duplicated the subsequence 1 4. In the second test case we started with 4 3 1 2, changed it into (4 3) 1 2 (4 3), then changed that sequence into 4 (3 1) 2 (3 1) 4 3, and finally changed that into 4 3 1 2 (3 1 4) 3 (3 1 4).*