Cho một hoán vị \(p\) gồm \(n\) số (từ \(1\) đến \(n\)).
Bạn có một deque (hàng đợi hai đầu) ban đầu rỗng.

Bạn sẽ duyệt qua các phần tử của hoán vị \(p\) theo đúng thứ tự, từ \(p_1\) đến \(p_n\). Với mỗi phần tử \(p_i\), bạn phải đưa nó vào đầu hoặc cuối deque.

Hãy tìm cách thêm phần tử để deque cuối cùng (sau khi đã thêm \(n\) phần tử) là dãy có thứ tự từ điển nhỏ nhất có thể.

(Lưu ý: Dãy \(x\) nhỏ hơn dãy \(y\) theo thứ tự từ điển nếu tại vị trí \(i\) đầu tiên mà chúng khác nhau, ta có \(x_i < y_i\). VD: \([1,2,3] < [1,2,4]\))

Ràng buộc

• \(1 \le t \le 1000\) (Số lượng test cases).
• \(1 \le n \le 2 \times 10^5\) (Kích thước hoán vị).
• \(1 \le p_i \le n\) (Các phần tử \(p_i\) là duy nhất).
• Tổng của \(n\) trên tất cả các test cases không vượt quá \(2 \times 10^5\).

Input

• Dòng đầu tiên chứa số nguyên \(t\) — số lượng test cases.
• Mỗi test case được mô tả bởi \(2t\) dòng tiếp theo:
  • Dòng đầu tiên của test case chứa số nguyên \(n\).
  • Dòng thứ hai chứa \(n\) số nguyên \(p_1, p_2, \dots, p_n\) — hoán vị \(p\).

Output

• Với mỗi test case, in ra \(n\) số nguyên trên một dòng — dãy có thứ tự từ điển nhỏ nhất có thể thu được trong deque.

VíDụ

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

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