Anh nông dân John có một hoán vị \(p\) có độ dài \(N\) (\(2 \leq N \leq 10^5\)) bao gồm những số nguyên dương từ \(1\) đến \(N\) tượng trưng cho mã gen siêu bò của anh ấy. Do ghen tị với đàn bò nhà anh John, nông dân Nhoj đã đột nhập vào nông trại của John và phá hỏng hoán vị mẫu khiến cho John không thể lai tạo thêm siêu bò. Tuy nhiên do chút tình người còn sót lại, Nhoj đã để lại một số gợi ý để giúp John khôi phục hoán vị của anh ấy. Nhiệm vụ của bạn là giúp nông dân John khôi phục lại hoán vị có thứ tự từ điển nhỏ nhất với ít nhất một phần tử còn lại theo các bước như sau:

Giả sử những gì còn sót lại của hoán vị là \(p'_1, p'_2, ..., p'_n\).

• Nếu \(p'_1 > p'_n\), ghi lại \(p'_2\) và loại bỏ \(p'_1\) khỏi hoán vị
• Ngược lại thì ghi lại \(p'_{n-1}\) và loại bỏ \(p'_n\) khỏi hoán vị.

Sau khi phá bĩnh, nông dân Nhoj đã viết lại \(N - 1\) số nguyên \(h_1, h_2, ..., h_{N-1}\) để giúp John khôi phục hoán vị nhanh hơn. Hãy giúp John khôi phục lại hoán vị hoặc chi ra nếu Nhoj đã mắc lỗi trong việc để lại gợi ý. Lưu ý rằng một hoán vị sẽ nhỏ hơn theo thứ tự từ điển nếu nó nhỏ hơn hoán vị còn lại tại vị trí khác biệt đầu tiên \(i\) giữa hai hoán vị.

Input:

• Dòng đầu tiên chứa \(T\) là số lượng test case (\(1 \leq T \leq 10\)).
• Mỗi test case gồm 2 dòng, dòng thứ nhất chứa số nguyên \(N\) (\(2 \leq N \leq 10^5\)) và dòng thứ 2 chứa \(N - 1\) số nguyên \(h_1, h_2, ... h_{N-1}\) (\(1 \leq h_i \leq N\)).

Output:

• In ra \(T\) dòng đại diện cho kết quả của mỗi test case, trong đó, mỗi dòng in ra kết quả của hoán vị \(p\) sau khi khôi phục hoặc -1 nếu không thể khôi phục.

Scoring:

• Subtask 1: \(N \leq 8\)
• Subtask 2: \(N \leq 100\)
• Subtask 3: Không có ràng buộc gì thêm.

Example:

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

1 2
-1
-1
3 1 2 4
1 2 3 4