Tahp vừa khám phá ra một thuật toán thú vị với các ngăn xếp đơn điệu. Cậu bắt đầu với một dãy số yêu thích ~p_1, p_2, \ldots, p_n~ là hoán vị của các số nguyên từ ~1~ đến ~n~ và một dãy vô hạn các ngăn xếp (stack) được đánh số từ ~1~. Ban đầu, các ngăn xếp đều rỗng.

Cậu định nghĩa thuật toán đệ quy để thêm một phần tử có giá trị ~x~ vào ngăn xếp thứ ~i~ như sau:

function add(i, x):
    while (stack[i] is not empty) and (x < top(stack[i])) do
        y := top(stack[i])
        pop(stack[i])
        add(i + 1, y)
    end while
    push(stack[i], x)
end function

Tahp sẽ lần lượt thêm các phần tử của dãy ~p~ vào ngăn xếp số ~1~, tức là gọi liên tiếp các thao tác: ~\texttt{add(1, $p_1$)}, \texttt{add(1, $p_2$)}, \ldots, \texttt{add(1, $p_n$)}~

Sau khi quá trình trên kết thúc, cậu ghi lại trạng thái của toàn bộ dãy ~n~ ngăn xếp, ký hiệu là ~s(p)~. Tahp nhận thấy rằng có nhiều dãy ~p~ khác nhau nhưng đều tạo ra cùng một trạng thái.

Giờ đây, Tahp muốn thử thách bạn tìm một hoán vị ~q_1, q_2, \ldots, q_n~ sao cho:

• ~q > p~ theo thứ tự từ điển~^*~

• ~s(q) = s(p)~

Nếu không tồn tại hoán vị nào như vậy, hãy kết luận rằng không thể tìm được. Hai trạng thái được xem là giống nhau nếu với mọi ngăn xếp, dãy các phần tử trong ngăn xếp đó giống hệt nhau theo thứ tự từ dưới lên trên.

Hơn nữa, Tahp có những yêu cầu khác nhau cho hoán vị ~q~ cần tìm, được mô tả bằng số nguyên ~k \in \{0, 1\}~:

• Nếu ~k = 0~: ~q~ là một hoán vị bất kỳ thoả mãn.

• Nếu ~k = 1~: ~q~ là hoán vị nhỏ nhất theo thứ tự từ điển trong tất cả các hoán vị thoả mãn. Nói cách khác, không tồn tại hoán vị ~q'~ nào thoả mãn các điều kiện trên mà ~q' < q~

——————————————————

~^*~Với hai hoán vị ~p~ và ~q~ khác nhau cùng có độ dài ~n~, ta nói ~q~ nhỏ hơn ~p~ theo thứ tự từ điển nếu ~q_i < p_i~, với ~i~ là vị trí đầu tiên mà ~p_i \neq q_i~.

Input

Dòng đầu tiên chứa số nguyên ~t~ (~1 \le t \le 10\,000~)  – số lượng test case. Mô tả của mỗi test case như sau.

Dòng đầu tiên chứa hai số nguyên ~n~, ~k~ ~(1 \le n \le 2 \cdot 10^5; k \in \{0, 1\})~  — độ dài dãy ~p~ và yêu cầu của Tahp.

Dòng thứ hai chứa ~n~ số nguyên ~p_1, p_2, \ldots, p_n~ ~(1 \le p_i \le n)~  — dãy số yêu thích của Tahp.

Đảm bảo dãy ~p~ là một hoán vị của các số nguyên từ ~1~ đến ~n~, và tổng ~n~ trong tất cả các test case không vượt quá ~10^5~.

Output

Với mỗi test case, nếu không tồn tại hoán vị nào thoả mãn yêu cầu, in ra ~\mathtt{-1}~. Ngược lại, in ra trên một dòng hoán vị ~q~ tìm được. Với ~k = 0~, nếu có nhiều hoán vị ~q~ thỏa mãn, hãy in ra hoán vị ~q~ bất kỳ.

Scoring

Sample Input 1

4
3 1
1 3 2
5 0
5 4 3 2 1
6 0
3 4 1 6 2 5
6 1
3 4 1 6 2 5

Sample Output 1

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

Notes

Ta kí hiệu ngăn xếp thứ ~i~ là ~s_i~, và ta sẽ không quan tâm đến các ngăn xếp rỗng.

Ở test case thứ nhất, ta xét quá trình thêm hoán vị ~[1, 3, 2]~ như sau:

• Khi ~\texttt{add(1, $p_1 = 1$)}~, ta có ~s_1 = [1]~.

• Khi ~\texttt{add(1, $p_2 = 3$)}~, vì ~3~ lớn hơn đầu ~s_1~ là ~1~, ta thêm ~3~ vào ~s_1~. ~s_1 = [1, 3]~.

• Khi ~\texttt{add(1, $p_3 = 2$)}~:

  • Vì ~2~ nhỏ hơn đầu ~s_1~ là ~3~, ta pop ~3~ ra khỏi ~s_1~ và thực hiện ~\texttt{add(2, $3$)}~. Sau thao tác này, ~s_1 = [1], s_2 = [3]~.

  • Bây giờ ~2~ lớn hơn đầu ~s_1~ là ~1~, ta thêm ~2~ vào ~s_1~. Sau thao tác này, ~s_1 = [1, 2], s_2 = [3]~.

Cuối cùng, ta có ~s_1 = [1, 2], s_2 = [3]~. Đây cũng là trạng thái của ~p = [1, 3, 2]~.

Bây giờ, ta xét quá trình thêm hoán vị ~[3, 1, 2]~ như sau:

• Khi ~\texttt{add(1, $p_1 = 3$)}~, ta có ~s_1 = [3]~.

• Khi ~\texttt{add(1, $p_2 = 1$)}~:

  • Vì ~1~ nhỏ hơn đầu ~s_1~ là ~3~, ta pop ~3~ ra khỏi ~s_1~ và thực hiện ~\texttt{add(2, $3$)}~. Sau thao tác này, ~s_1 = [], s_2 = [3]~.

  • Bây giờ ~s_1~ rỗng, nên ta thêm ~1~ vào ~s_1~. Sau thao tác này, ~s_1 = [1], s_2 = [3]~.

• Khi ~\texttt{add(1, $p_3 = 2$)}~, vì ~2~ lớn hơn đầu ~s_1~ là ~1~, ta thêm ~2~ vào ~s_1~. ~s_1 = [1, 2], s_2 = [3]~.

Cuối cùng, ta có ~s_1 = [1, 2], s_2 = [3]~. Đây cũng là trạng thái của ~p = [3, 1, 2]~.

Vì thế, ta thấy ~s([1, 3, 2]) = s([3, 1, 2])~. Ta có thể chứng minh được rằng không có hoán vị nào có giá trị từ điển giữa ~[1, 3, 2]~ và ~[3, 1, 2]~ mà cho ra trạng thái tương tự. Vì thế, do ~k = 1~ ở test case này, đáp án duy nhất được chấp nhận là ~q = [3, 1, 2]~.