ศาสตราจารย์เฉิน ผู้เชี่ยวชาญด้านอักษรโบราณเชิงคำนวณ ได้ใช้เวลาหลายปีศึกษาจารึกของราชวงศ์ ไร้ความซ้ำซ้อน (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