Tima came back from his journey to Xorland and brought back an array of $n$ integers. Xorland is a small country known for its food, music, and games on arrays. A peculiarity of Xorland’s games is that there is no winner: friendship always wins! One of such games is “Xor-Mat”.

Rules of “Xor-Mat” are simple. Two players, before the start of the game, choose an array $a$ and an integer $k$. Then, the first player paints each number in the array with one of the $k$ colors. Let $c_i$ be the color of $i$-th number in the array if we order the colors from $1$ to $k$. Second player, then, chooses a pair of indices $(i,j)$ such that $i \ne j$ and $c_i = c_j$.

The goal of the first player is to maximize $a_i \oplus a_j$, while, second player tries to minimize $a_i \oplus a_j$. Here, $\oplus$ is a bitwise “XOR” operation.

Mansur challenged Tima for a “Xor-Mat” game. They are playing on Tima’s array. Mansur goes first and Tima is second. Print the value of $a_i \oplus a_j$ when both players play optimally. Also, find out an optimal coloring of the array that Mansur might choose.

Input

The first line contains one integer $t$ ($1 \le t \le 5 \cdot 10^4$) — the number of test cases.

The $2 \cdot t$ lines follow in following pattern:

The first line of each test case contains two integers $n$ ($2 \le n \le 5 \cdot 10^4$) and $k$ ($1 \le k \le \min(n-1,50)$).

Second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1 \le a_i \le 10^9$) — Tima’s array.

It is guaranteed, that the sum of $n$ across all test cases does not exceed $5 \cdot 10^4$.

Output

For each test case in input print two lines:

• In the first line, print the value of $a_i \oplus a_j$ when both players play optimally.
• In the second line, print $n$ integers $c_1,c_2,\ldots,c_n$ ($1 \le c_i \le k$), where $c_i$ is equal to the color that Mansur chooses for $i$-th number of the array. If there are more than one possible ways to color the array optimally, print any of them.

Subtasks

Let $S$ be the sum of $n$ over all test cases.

Examples

Input 1

2
3 1
1 2 3
3 2
1 2 3

Output 1

1
1 1 1
3
1 1 2