Profesor Chen, seorang pakar terkemuka dalam Paleografi Komputasional, telah menghabiskan bertahun-tahun mempelajari naskah-naskah dari dinasti Non-Redundan. Para juru tulis pada era ini menganut doktrin estetika yang unik: mereka percaya bahwa sebuah teks kehilangan kekuatan spiritualnya jika mengandung "gema".

Dalam konteks ini, gema anagramatik didefinisikan sebagai dua segmen berbeda mana pun dari sebuah teks yang, meskipun urutannya tidak harus identik, mengandung simbol-simbol yang persis sama dengan jumlah yang persis sama. Untuk sebuah teks yang direpresentasikan sebagai barisan simbol, sebuah gema ada jika terdapat dua posisi awal berbeda $x$ dan $y$ sedemikian sehingga sublarik sepanjang $l$ yang dimulai pada $x$ merupakan permutasi dari sublarik sepanjang $l$ yang dimulai pada $y$. Sebagai contoh, perhatikan barisan $[1, 2, 1, 1, 3, 1, 2, 1]$. Segmen sepanjang $4$ yang dimulai pada posisi kedua, $[2, 1, 1, 3]$, dan segmen sepanjang $4$ yang dimulai pada posisi kelima, $[3, 1, 2, 1]$, membentuk sebuah gema anagramatik.

Profesor Chen telah menemukan beberapa gulungan semacam itu, tetapi banyak simbol telah memudar seiring waktu, menyisakan celah (direpresentasikan dengan $0$). Tugas Anda adalah mengisi celah-celah ini menggunakan simbol dari himpunan yang diizinkan $\{1, 2, \dots, k\}$ sedemikian sehingga Skor Disonansi (Dissonance Score) dari gulungan yang dihasilkan menjadi minimum. Skor Disonansi adalah panjang maksimum $l$ dari gema anagramatik mana pun yang ada dalam barisan yang telah dilengkapi.

Masukan

Terdapat beberapa kasus uji. Baris pertama masukan berisi sebuah bilangan bulat $T$ ($1 \le T \le 10^4$) yang menyatakan banyaknya kasus uji. Untuk setiap kasus uji:

Baris pertama berisi dua bilangan bulat $n$ dan $k$ ($2 \le n \le 2 \times 10^5$, $1 \le k \le n$).

Baris kedua berisi $n$ bilangan bulat $a_1, a_2, \dots, a_n$ ($0 \le a_i \le k$).

Dijamin bahwa jumlah $n$ di seluruh kasus uji tidak melebihi $2 \times 10^5$.

Keluaran

Untuk setiap kasus uji, keluarkan $n$ bilangan bulat $b_1, b_2, \dots, b_n$ ($1 \le b_i \le k$) yang merepresentasikan barisan yang telah dipulihkan. Barisan $b$ harus cocok dengan $a$ pada semua posisi dengan $a_i \neq 0$, dan harus mencapai Skor Disonansi minimum yang mungkin.

Jika terdapat beberapa cara untuk memulihkan gulungan secara optimal, Profesor Chen akan menerima cara mana pun.

Contoh

Masukan

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

Keluaran

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