Tima 从 Xorland 之旅归来，带回了一个包含 $n$ 个整数的数组。Xorland 是一个以美食、音乐和数组游戏闻名的小国。Xorland 游戏的特点是没有赢家：友谊第一！其中一个游戏叫做“Xor-Mat”。

“Xor-Mat”的规则很简单。两名玩家在游戏开始前选择一个数组 $a$ 和一个整数 $k$。然后，第一名玩家用 $k$ 种颜色中的一种为数组中的每个数字涂色。如果我们按 $1$ 到 $k$ 对颜色进行编号，令 $c_i$ 为第 $i$ 个数字的颜色。随后，第二名玩家选择一对下标 $(i, j)$，满足 $i \neq j$ 且 $c_i = c_j$。

第一名玩家的目标是最大化 $a_i \oplus a_j$，而第二名玩家则试图最小化 $a_i \oplus a_j$。其中 $\oplus$ 表示按位“异或”运算。

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, \dots, 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, \dots, 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