Với một xâu $s$ có độ dài $n$, ta định nghĩa $p_j = x$ nếu $s[x \dots j]$ là hậu tố nhỏ nhất của $s[1 \dots j]$, với mọi $j = 1, \dots, n$. (Một hậu tố được gọi là hậu tố nhỏ nhất của một xâu nếu nó nhỏ hơn về mặt từ điển so với bất kỳ hậu tố nào khác của xâu đó.)

Bạn cần khôi phục $s$ từ $p_1, \dots, p_n$. Nếu có nhiều đáp án, hãy tìm xâu nhỏ nhất về mặt từ điển.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên duy nhất $T$ ($1 \le T \le 10^5$) đại diện cho số lượng bộ dữ liệu. Đối với mỗi bộ dữ liệu, dòng đầu tiên chứa một số nguyên duy nhất $n$ ($1 \le n \le 3 \times 10^6$) đại diện cho độ dài của $s$. Dòng tiếp theo chứa $n$ số nguyên $p_1, \dots, p_n$ ($1 \le p_i \le i$ với mọi $1 \le i \le n$). Đảm bảo rằng tổng của $n$ trên tất cả các bộ dữ liệu không vượt quá $3 \times 10^6$.

Dữ liệu ra

Đối với mỗi bộ dữ liệu, in ra một dòng. Nếu không có lời giải, in ra $-1$. Nếu có, in ra xâu $s$ nhỏ nhất về mặt từ điển. Các ký tự của $s$ được biểu diễn bằng các số nguyên dương. Số nguyên nhỏ hơn đại diện cho ký tự nhỏ hơn trong thứ tự từ điển.

Ví dụ

Dữ liệu vào 1

6
3
1 1 1
3
1 1 2
3
1 1 3
3
1 2 1
3
1 2 2
3
1 2 3

Dữ liệu ra 1

1 2 2
-1
1 2 1
1 1 2
2 1 2
1 1 1

Ghi chú

Vì dữ liệu vào/ra có thể rất lớn, bạn nên sử dụng các phương pháp nhập/xuất nhanh.