Giáo sư Chen, một chuyên gia lỗi lạc trong lĩnh vực Cổ tự học Tính toán, đã dành nhiều năm nghiên cứu các văn tự của triều đại Phi Dư Thừa (Non-Redundant). Các thư lại thời kỳ này tuân theo một học thuyết thẩm mỹ kỳ lạ: họ tin rằng một văn bản sẽ mất đi linh lực nếu chứa những "tiếng vọng".

Trong ngữ cảnh này, một tiếng vọng hoán vị (anagrammatic echo) được định nghĩa là hai đoạn phân biệt bất kỳ của văn bản mà tuy không nhất thiết giống hệt nhau về thứ tự, nhưng chứa cùng các ký hiệu với số lượng hoàn toàn giống nhau. Đối với một văn bản được biểu diễn dưới dạng một dãy ký hiệu, tiếng vọng tồn tại nếu có hai vị trí bắt đầu khác nhau $x$ và $y$ sao cho dãy con độ dài $l$ bắt đầu tại $x$ là một hoán vị của dãy con độ dài $l$ bắt đầu tại $y$. Ví dụ, xét dãy $[1, 2, 1, 1, 3, 1, 2, 1]$. Đoạn độ dài $4$ bắt đầu tại vị trí thứ hai, $[2, 1, 1, 3]$, và đoạn độ dài $4$ bắt đầu tại vị trí thứ năm, $[3, 1, 2, 1]$, tạo thành một tiếng vọng hoán vị.

Giáo sư Chen đã khai quật được một số cuộn thư như vậy, nhưng nhiều ký hiệu đã phai mờ theo thời gian, để lại các khoảng trống (được biểu diễn bởi $0$). Nhiệm vụ của bạn là điền vào các khoảng trống này bằng các ký hiệu từ tập cho phép $\{1, 2, \dots, k\}$ sao cho Điểm Bất Hòa (Dissonance Score) của cuộn thư thu được là nhỏ nhất. Điểm Bất Hòa là độ dài lớn nhất $l$ của bất kỳ tiếng vọng hoán vị nào xuất hiện trong dãy đã hoàn thiện.

Dữ liệu vào

Có nhiều bộ dữ liệu. Dòng đầu tiên chứa một số nguyên $T$ ($1 \le T \le 10^4$) cho biết số lượng bộ dữ liệu. Với mỗi bộ dữ liệu:

Dòng đầu tiên chứa hai số nguyên $n$ và $k$ ($2 \le n \le 2 \times 10^5$, $1 \le k \le n$).

Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \dots, a_n$ ($0 \le a_i \le k$).

Đảm bảo tổng của $n$ trên tất cả các bộ dữ liệu không vượt quá $2 \times 10^5$.

Kết quả

Với mỗi bộ dữ liệu, in ra $n$ số nguyên $b_1, b_2, \dots, b_n$ ($1 \le b_i \le k$) biểu diễn dãy đã được phục원. Dãy $b$ phải khớp với $a$ tại mọi vị trí mà $a_i \neq 0$, và phải đạt được Điểm Bất Hòa nhỏ nhất có thể.

Nếu có nhiều cách phục hồi cuộn thư một cách tối ưu, Giáo sư Chen sẽ chấp nhận bất kỳ cách nào.

Ví dụ

Dữ liệu vào

4
8 3
0 1 0 2 1 3 0 2
3 3
1 0 2
9 7
0 1 1 0 5 0 4 0 7
6 6
0 0 0 0 0 0

Kết quả

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