قضى البروفيسور تشين، وهو خبير بارز في علم الخطوط القديمة الحاسوبي، سنواتٍ في دراسة مخطوطات سلالة عدم التكرار (Non-Redundant). اتّبع الكتبة في تلك الحقبة عقيدةً جماليةً فريدة: إذ اعتقدوا أن النص يفقد قوّته الروحية إذا احتوى على «أصداء».

في هذا السياق، يُعرَّف الصدى التبديلي (anagrammatic echo) بأنه أي مقطعين مختلفين من النص يحتويان — وإن لم يتطابقا بالضرورة في الترتيب — على الرموز نفسها تمامًا وبالكميات نفسها تمامًا. وبالنسبة لنص مُمثَّل كمتتالية من الرموز، يوجد صدى إذا وُجد موقعا بداية مختلفان $x$ و $y$ بحيث تكون المصفوفة الفرعية التي طولها $l$ وتبدأ عند $x$ تبديلًا للمصفوفة الفرعية التي طولها $l$ وتبدأ عند $y$. على سبيل المثال، لنأخذ المتتالية $[1, 2, 1, 1, 3, 1, 2, 1]$. إن المقطع الذي طوله $4$ ويبدأ عند الموقع الثاني $[2, 1, 1, 3]$، والمقطع الذي طوله $4$ ويبدأ عند الموقع الخامس $[3, 1, 2, 1]$، يشكّلان معًا صدىً تبديليًا.

اكتشف البروفيسور تشين عدة لفائف من هذا النوع، غير أن كثيرًا من الرموز قد بهتت بمرور الزمن تاركةً فجوات (يُمثَّل عنها بالرقم $0$). مهمتك هي ملء هذه الفجوات باستخدام رموز من المجموعة المسموح بها $\{1, 2, \dots, k\}$ بحيث تكون درجة التنافر (Dissonance Score) الناتجة للفافة أصغر ما يمكن. وتُعرَّف درجة التنافر بأنها أقصى طول $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$ في جميع المواقع التي يكون فيها $a_i \neq 0$، ويجب أن تحقق أقل درجة تنافر ممكنة.

إذا كانت هناك عدة طرق لاستعادة اللفافة بشكل أمثل، فسيقبل البروفيسور تشين أيًّا منها.

مثال

الإدخال

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