Tima pulang dari perjalanannya ke Xorland dengan membawa sebuah larik berisi $n$ bilangan bulat. Xorland adalah sebuah negara kecil yang terkenal dengan makanan, musik, dan permainan pada larik. Keunikan permainan Xorland adalah tidak adanya pemenang: persahabatan selalu menang! Salah satu permainan tersebut adalah “Xor-Mat”.

Aturan “Xor-Mat” sederhana. Sebelum permainan dimulai, dua pemain memilih sebuah larik $a$ dan sebuah bilangan bulat $k$. Kemudian, pemain pertama mewarnai setiap bilangan dalam larik dengan salah satu dari $k$ warna. Misalkan $c_i$ adalah warna bilangan ke-$i$ dalam larik jika warna diberi nomor dari $1$ hingga $k$. Pemain kedua kemudian memilih sepasang indeks $(i,j)$ sedemikian sehingga $i \ne j$ dan $c_i=c_j$.

Tujuan pemain pertama adalah memaksimalkan $a_i \oplus a_j$, sedangkan pemain kedua berusaha meminimalkan $a_i \oplus a_j$. Di sini, $\oplus$ adalah operasi “XOR” bit demi bit.

Mansur menantang Tima bermain “Xor-Mat”. Mereka bermain menggunakan larik milik Tima. Mansur menjadi pemain pertama dan Tima menjadi pemain kedua. Cetak nilai $a_i \oplus a_j$ ketika kedua pemain bermain secara optimal. Temukan pula suatu pewarnaan optimal yang dapat dipilih Mansur untuk larik tersebut.

Masukan

Baris pertama berisi sebuah bilangan bulat $t$ ($1 \le t \le 5\cdot 10^4$), yaitu banyaknya kasus uji.

Selanjutnya terdapat $2\cdot t$ baris dengan pola berikut:

Baris pertama setiap kasus uji berisi dua bilangan bulat $n$ ($2 \le n \le 5\cdot 10^4$) dan $k$ ($1 \le k \le \min(n-1,50)$).

Baris kedua setiap kasus uji berisi $n$ bilangan bulat $a_1,a_2,\ldots,a_n$ ($1 \le a_i \le 10^9$), yaitu larik milik Tima.

Dijamin bahwa jumlah $n$ untuk seluruh kasus uji tidak melebihi $5\cdot 10^4$.

Keluaran

Untuk setiap kasus uji dalam masukan, cetak dua baris:

• Pada baris pertama, cetak nilai $a_i \oplus a_j$ ketika kedua pemain bermain secara optimal.
• Pada baris kedua, cetak $n$ bilangan bulat $c_1,c_2,\ldots,c_n$ ($1 \le c_i \le k$), dengan $c_i$ menyatakan warna yang dipilih Mansur untuk bilangan ke-$i$ dalam larik. Jika terdapat lebih dari satu cara mewarnai larik secara optimal, cetak salah satunya.

Subtugas

Misalkan $S$ adalah jumlah $n$ untuk seluruh kasus uji.

Contoh

Masukan 1

2
3 1
1 2 3
3 2
1 2 3

Keluaran 1

1
1 1 1
3
1 1 2