Cho một hoán vị $p$ của $1\sim n$.

Bạn cần xây dựng một dãy $a$ có độ dài $n$ thỏa mãn:

• Mỗi phần tử của dãy $a$ là một số nguyên dương không lớn hơn $n$.
• Không tồn tại cặp số nguyên có thứ tự $(l,r)$ thỏa mãn $1 \le l \le r \le n$ và $\sum\limits_{i=l}^r a_i=\sum\limits_{i=l}^r p_i$.

Hoặc thông báo rằng không có lời giải.

Ở đây, hoán vị của $1\sim n$ là một dãy mà mỗi số nguyên dương không lớn hơn $n$ xuất hiện đúng một lần.

Dữ liệu vào

Bài toán có nhiều bộ dữ liệu kiểm tra.

Dòng đầu tiên chứa một số nguyên $T$, cho biết số bộ dữ liệu kiểm tra.

Tiếp theo là lần lượt các bộ dữ liệu kiểm tra. Với mỗi bộ:

• Dòng đầu tiên chứa một số nguyên $n$.
• Dòng thứ hai chứa $n$ số nguyên biểu diễn hoán vị $p$ đã cho.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một dòng:

• Nếu tồn tại dãy $a$ thỏa mãn điều kiện, in ra $n$ số nguyên cách nhau bởi dấu cách, biểu diễn dãy $a$ mà bạn xây dựng.
• Nếu không tồn tại dãy $a$ thỏa mãn điều kiện, in ra $-1$.

Mọi kết quả thỏa mãn yêu cầu đều được chấp nhận.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

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

Ghi chú

Với bộ dữ liệu thứ $1$, cả $\{1,3,3\}$ và $\{1,1,3\}$ đều là các dãy $a$ thỏa mãn điều kiện.

Với bộ dữ liệu thứ $2$, có thể chứng minh rằng không tồn tại dãy $a$ thỏa mãn điều kiện.

Với bộ dữ liệu thứ $3$, ngoài $\{5,3,2,1,1 \}$, các dãy $a$ như $\{3,4,5,3,2 \}$, $\{1,4,5,3,4 \}$, $\{5,3,3,4,5\}$ cũng thỏa mãn điều kiện.

Giới hạn

Gọi $\sum n$ là tổng các giá trị $n$ trong một tệp kiểm tra.

Với tất cả dữ liệu, $1 \le T \le 5000$, $2 \le n \le 10^6$, $\sum n \le 10^6$, và đảm bảo rằng $p$ là một hoán vị của $1\sim n$.