Tima wrócił z podróży do Xorland i przywiózł tablicę $n$ liczb całkowitych. Xorland to mały kraj znany z jedzenia, muzyki i gier na tablicach. Osobliwością gier w Xorland jest brak zwycięzcy: zawsze wygrywa przyjaźń! Jedną z takich gier jest „Xor-Mat”.

Zasady „Xor-Mat” są proste. Dwaj gracze przed rozpoczęciem gry wybierają tablicę $a$ i liczbę całkowitą $k$. Następnie pierwszy gracz koloruje każdą liczbę w tablicy jednym z $k$ kolorów. Niech $c_i$ będzie kolorem $i$-tej liczby w tablicy, gdy kolory ponumerujemy od $1$ do $k$. Drugi gracz wybiera następnie parę indeksów $(i,j)$ taką, że $i \ne j$ i $c_i=c_j$.

Celem pierwszego gracza jest zmaksymalizowanie $a_i \oplus a_j$, natomiast drugi gracz próbuje zminimalizować $a_i \oplus a_j$. Symbol $\oplus$ oznacza bitową operację „XOR”.

Mansur wyzwał Timę na grę w „Xor-Mat”. Grają na tablicy Timy. Mansur jest pierwszym graczem, a Tima drugim. Wypisz wartość $a_i \oplus a_j$, gdy obaj gracze grają optymalnie. Znajdź również optymalne kolorowanie tablicy, które może wybrać Mansur.

Wejście

Pierwszy wiersz zawiera jedną liczbę całkowitą $t$ ($1 \le t \le 5 \cdot 10^4$) — liczbę przypadków testowych.

Następnie występuje $2 \cdot t$ wierszy według poniższego schematu:

Pierwszy wiersz każdego przypadku testowego zawiera dwie liczby całkowite $n$ ($2 \le n \le 5 \cdot 10^4$) i $k$ ($1 \le k \le \min(n-1,50)$).

Drugi wiersz każdego przypadku testowego zawiera $n$ liczb całkowitych $a_1,a_2,\ldots,a_n$ ($1 \le a_i \le 10^9$) — tablicę Timy.

Gwarantuje się, że suma $n$ we wszystkich przypadkach testowych nie przekracza $5 \cdot 10^4$.

Wyjście

Dla każdego przypadku testowego z wejścia wypisz dwa wiersze:

• W pierwszym wierszu wypisz wartość $a_i \oplus a_j$, gdy obaj gracze grają optymalnie.
• W drugim wierszu wypisz $n$ liczb całkowitych $c_1,c_2,\ldots,c_n$ ($1 \le c_i \le k$), gdzie $c_i$ jest kolorem wybranym przez Mansura dla $i$-tej liczby w tablicy. Jeśli istnieje więcej niż jeden sposób optymalnego pokolorowania tablicy, wypisz dowolny z nich.

Podzadania

Niech $S$ będzie sumą $n$ we wszystkich przypadkach testowych.

Przykład

Wejście 1

2
3 1
1 2 3
3 2
1 2 3

Wyjście 1

1
1 1 1
3
1 1 2