Есептеу палеографиясы саласының көрнекті маманы профессор Чэнь Артықшылықсыз (Non-Redundant) әулетінің жазбаларын зерттеуге көп жыл арнады. Сол дәуірдің хатшылары ерекше эстетикалық қағиданы ұстанған: олар мәтінде «жаңғырықтар» болса, ол өзінің рухани күшін жоғалтады деп сенген.

Бұл контексте анаграммалық жаңғырық деп реті жағынан міндетті түрде бірдей болмаса да, дәл бірдей таңбаларды дәл бірдей мөлшерде қамтитын мәтіннің кез келген екі түрлі бөлігі аталады. Таңбалар тізбегі ретінде берілген мәтін үшін, егер $x$ позициясынан басталатын ұзындығы $l$ ішкі массив $y$ позициясынан басталатын ұзындығы $l$ ішкі массивтің орын ауыстыруы (пермутациясы) болатындай екі түрлі бастапқы $x$ және $y$ позициялары табылса, жаңғырық бар болады. Мысалы, $[1, 2, 1, 1, 3, 1, 2, 1]$ тізбегін қарастырайық. Екінші позициядан басталатын ұзындығы $4$ бөлік $[2, 1, 1, 3]$ пен бесінші позициядан басталатын ұзындығы $4$ бөлік $[3, 1, 2, 1]$ анаграммалық жаңғырық құрайды.

Профессор Чэнь осындай бірнеше шиыршық қолжазбаны тапты, бірақ уақыт өте келе көптеген таңбалар өшіп, бос орындар ($0$ санымен белгіленген) қалған. Сіздің міндетіңіз — шиыршықтың нәтижелік Диссонанс ұпайы (Dissonance Score) барынша аз болатындай етіп, осы бос орындарды рұқсат етілген $\{1, 2, \dots, k\}$ жиынындағы таңбалармен толтыру. Диссонанс ұпайы — толықтырылған тізбекте кездесетін кез келген анаграммалық жаңғырықтың ең үлкен $l$ ұзындығы.

Кіріс деректер

Бірнеше тест жиынтығы берілген. Кірістің бірінші жолында тест жиынтықтарының санын білдіретін бүтін $T$ ($1 \le T \le 10^4$) саны берілген. Әрбір тест жиынтығы үшін:

Бірінші жолда екі бүтін $n$ және $k$ ($2 \le n \le 2 \times 10^5$, $1 \le k \le n$) сандары берілген.

Екінші жолда $n$ бүтін $a_1, a_2, \dots, a_n$ ($0 \le a_i \le k$) сандары берілген.

Барлық тест жиынтықтары бойынша $n$ мәндерінің қосындысы $2 \times 10^5$ шамасынан аспайтынына кепілдік беріледі.

Шығыс деректер

Әрбір тест жиынтығы үшін қалпына келтірілген тізбекті білдіретін $n$ бүтін $b_1, b_2, \dots, b_n$ ($1 \le b_i \le k$) сандарын шығарыңыз. $b$ тізбегі $a_i \neq 0$ болатын барлық позицияларда $a$ тізбегімен сәйкес келуі тиіс және мүмкін болатын ең аз Диссонанс ұпайына қол жеткізуі керек.

Егер шиыршықты оңтайлы қалпына келтірудің бірнеше жолы болса, профессор Чэнь олардың кез келгенін қабылдайды.

Мысал

Кіріс деректер

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

Шығыс деректер

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