פרופסור צ'ן, מומחה בעל שם לפלאוגרפיה חישובית, הקדיש שנים לחקר כתבי שושלת אי-היתירות (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