Tima は Xorland への旅から帰り、$n$ 個の整数からなる配列を持ち帰りました。Xorland は、食べ物、音楽、そして配列を使ったゲームで知られる小さな国です。Xorland のゲームには、勝者がいないという特徴があります。いつも友情が勝つのです！そのようなゲームの一つが「Xor-Mat」です。

「Xor-Mat」のルールは簡単です。2 人のプレイヤーは、ゲームの開始前に配列 $a$ と整数 $k$ を選びます。その後、先手は配列の各数を $k$ 色のうちのいずれかで塗ります。色に $1$ から $k$ までの番号を付けたとき、配列の $i$ 番目の数の色を $c_i$ とします。続いて、後手は $i \ne j$ かつ $c_i=c_j$ を満たす添字の組 $(i,j)$ を選びます。

先手の目的は $a_i \oplus a_j$ を最大化することであり、後手は $a_i \oplus a_j$ を最小化しようとします。ここで、$\oplus$ はビット単位の排他的論理和「XOR」演算です。

Mansur は Tima に「Xor-Mat」での対戦を挑みました。2 人は Tima の配列を使って対戦します。Mansur が先手、Tima が後手です。両者が最適にプレイしたときの $a_i \oplus a_j$ の値を出力してください。また、Mansur が選び得る最適な配列の塗り分けも求めてください。

入力

最初の行には、テストケース数を表す整数 $t$ ($1 \le t \le 5 \cdot 10^4$) が与えられます。

続く $2 \cdot t$ 行は、次の形式で与えられます。

各テストケースの最初の行には、2 つの整数 $n$ ($2 \le n \le 5 \cdot 10^4$) と $k$ ($1 \le k \le \min(n-1,50)$) が与えられます。

各テストケースの 2 行目には、Tima の配列を表す $n$ 個の整数 $a_1,a_2,\ldots,a_n$ ($1 \le a_i \le 10^9$) が与えられます。

すべてのテストケースにわたる $n$ の総和は $5 \cdot 10^4$ 以下であることが保証されます。

出力

入力の各テストケースについて、2 行を出力してください。

• 1 行目には、両者が最適にプレイしたときの $a_i \oplus a_j$ の値を出力してください。
• 2 行目には、$n$ 個の整数 $c_1,c_2,\ldots,c_n$ ($1 \le c_i \le k$) を出力してください。ここで $c_i$ は、Mansur が配列の $i$ 番目の数に選ぶ色です。配列を最適に塗り分ける方法が複数ある場合は、そのうちどれを出力してもかまいません。

小課題

すべてのテストケースにわたる $n$ の総和を $S$ とします。

入出力例

入力 1

2
3 1
1 2 3
3 2
1 2 3

出力 1

1
1 1 1
3
1 1 2