Tima 從 Xorland 旅行歸來，帶回了一個由 $n$ 個整數組成的陣列。Xorland 是個以美食、音樂和陣列遊戲聞名的小國。Xorland 的遊戲有個特點：沒有贏家，友誼永遠獲勝！其中一種遊戲叫作「Xor-Mat」。

「Xor-Mat」的規則很簡單。兩名玩家在遊戲開始前選定一個陣列 $a$ 和一個整數 $k$。接著，第一名玩家用 $k$ 種顏色之一為陣列中的每個數字上色。若將顏色從 $1$ 到 $k$ 編號，令 $c_i$ 表示陣列中第 $i$ 個數字的顏色。之後，第二名玩家選擇一對索引 $(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