Tima กลับมาจากการเดินทางไปยัง Xorland พร้อมกับอาร์เรย์ของจำนวนเต็ม $n$ ตัว Xorland เป็นประเทศเล็ก ๆ ที่มีชื่อเสียงด้านอาหาร ดนตรี และเกมเกี่ยวกับอาร์เรย์ ลักษณะพิเศษของเกมใน Xorland คือไม่มีผู้ชนะ เพราะมิตรภาพชนะเสมอ! หนึ่งในเกมเหล่านั้นคือ “Xor-Mat”

กติกาของ “Xor-Mat” นั้นเรียบง่าย ก่อนเริ่มเกม ผู้เล่นสองคนเลือกอาร์เรย์ $a$ และจำนวนเต็ม $k$ จากนั้นผู้เล่นคนแรกระบายสีจำนวนแต่ละตัวในอาร์เรย์ด้วยสีใดสีหนึ่งจาก $k$ สี ให้ $c_i$ เป็นสีของจำนวนตัวที่ $i$ ในอาร์เรย์ เมื่อกำหนดหมายเลขสีตั้งแต่ $1$ ถึง $k$ จากนั้นผู้เล่นคนที่สองเลือกคู่ดัชนี $(i, j)$ ที่ $i \ne j$ และ $c_i = c_j$

เป้าหมายของผู้เล่นคนแรกคือทำให้ $a_i \oplus a_j$ มีค่ามากที่สุด ขณะที่ผู้เล่นคนที่สองพยายามทำให้ $a_i \oplus a_j$ มีค่าน้อยที่สุด ในที่นี้ $\oplus$ คือการดำเนินการ “XOR” แบบบิตต่อบิต

Mansur ท้า Tima เล่นเกม “Xor-Mat” ทั้งสองใช้อาร์เรย์ของ Tima โดย Mansur เป็นผู้เล่นคนแรก และ Tima เป็นผู้เล่นคนที่สอง จงแสดงค่าของ $a_i \oplus a_j$ เมื่อผู้เล่นทั้งสองเล่นอย่างเหมาะสมที่สุด พร้อมทั้งหาวิธีระบายสีอาร์เรย์อย่างเหมาะสมที่สุดที่ Mansur สามารถเลือกได้

ข้อมูลนำเข้า

บรรทัดแรกมีจำนวนเต็มหนึ่งตัว $t$ ($1 \le t \le 5 \cdot 10^4$) — จำนวนกรณีทดสอบ

จากนั้นมี $2 \cdot t$ บรรทัดในรูปแบบต่อไปนี้:

บรรทัดแรกของแต่ละกรณีทดสอบมีจำนวนเต็มสองตัว $n$ ($2 \le n \le 5 \cdot 10^4$) และ $k$ ($1 \le k \le \min(n - 1, 50)$)

บรรทัดที่สองของแต่ละกรณีทดสอบมีจำนวนเต็ม $n$ ตัว $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — อาร์เรย์ของ Tima

รับประกันว่าผลรวมของ $n$ ในทุกกรณีทดสอบไม่เกิน $5 \cdot 10^4$

ข้อมูลส่งออก

สำหรับแต่ละกรณีทดสอบในข้อมูลนำเข้า ให้แสดงผลสองบรรทัด:

• ในบรรทัดแรก แสดงค่าของ $a_i \oplus a_j$ เมื่อผู้เล่นทั้งสองเล่นอย่างเหมาะสมที่สุด
• ในบรรทัดที่สอง แสดงจำนวนเต็ม $n$ ตัว $c_1, c_2, \ldots, c_n$ ($1 \le c_i \le k$) โดย $c_i$ คือสีที่ Mansur เลือกให้จำนวนตัวที่ $i$ ในอาร์เรย์ หากมีวิธีระบายสีอาร์เรย์อย่างเหมาะสมที่สุดได้หลายวิธี ให้แสดงวิธีใดก็ได้

งานย่อย

ให้ $S$ เป็นผลรวมของ $n$ ในทุกกรณีทดสอบ

ตัวอย่าง

ข้อมูลนำเข้า 1

2
3 1
1 2 3
3 2
1 2 3

ข้อมูลส่งออก 1

1
1 1 1
3
1 1 2