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$ 嘅總和。
| 子任務 | 額外限制 | 分數 | 必須通過嘅子任務 |
|---|---|---|---|
| $0$ | 樣例 | $0$ | — |
| $1$ | $S \le 10, k \le 5$ | $6$ | $0$ |
| $2$ | $S \le 50000, k=1$ | $10$ | |
| $3$ | $S \le 1000, k \le 2$ | $10$ | — |
| $4$ | $S \le 50000, k \le 2$ | $20$ | $2,3$ |
| $5$ | $S \le 50000, k \le 4$ | $22$ | $1,4$ |
| $6$ | — | $32$ | $5$ |
樣例
輸入格式 1
2 3 1 1 2 3 3 2 1 2 3
輸出格式 1
1 1 1 1 3 1 1 2