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