Tima est revenu de son voyage à Xorland et en a rapporté un tableau de $n$ entiers. Xorland est un petit pays connu pour sa cuisine, sa musique et ses jeux sur les tableaux. Une particularité des jeux de Xorland est qu'il n'y a pas de vainqueur : l'amitié gagne toujours ! L'un de ces jeux est « Xor-Mat ».
Les règles de « Xor-Mat » sont simples. Avant le début de la partie, deux joueurs choisissent un tableau $a$ et un entier $k$. Ensuite, le premier joueur colorie chaque nombre du tableau avec l'une des $k$ couleurs. Soit $c_i$ la couleur du $i$-ème nombre du tableau, les couleurs étant numérotées de $1$ à $k$. Le second joueur choisit alors une paire d'indices $(i,j)$ telle que $i \ne j$ et $c_i=c_j$.
Le but du premier joueur est de maximiser $a_i \oplus a_j$, tandis que le second joueur cherche à minimiser $a_i \oplus a_j$. Ici, $\oplus$ est l'opération « XOR » bit à bit.
Mansur a défié Tima à une partie de « Xor-Mat ». Ils jouent sur le tableau de Tima. Mansur est le premier joueur et Tima le second. Affichez la valeur de $a_i \oplus a_j$ lorsque les deux joueurs jouent de façon optimale. Trouvez également une coloration optimale du tableau que Mansur pourrait choisir.
Entrée
La première ligne contient un entier $t$ ($1 \le t \le 5\cdot10^4$) — le nombre de cas de test.
Les $2\cdot t$ lignes suivantes suivent le schéma ci-dessous :
La première ligne de chaque cas de test contient deux entiers $n$ ($2 \le n \le 5\cdot10^4$) et $k$ ($1 \le k \le \min(n-1,50)$).
La seconde ligne de chaque cas de test contient $n$ entiers $a_1,a_2,\ldots,a_n$ ($1 \le a_i \le 10^9$) — le tableau de Tima.
Il est garanti que la somme de $n$ sur tous les cas de test ne dépasse pas $5\cdot10^4$.
Sortie
Pour chaque cas de test de l'entrée, affichez deux lignes :
- Sur la première ligne, affichez la valeur de $a_i \oplus a_j$ lorsque les deux joueurs jouent de façon optimale.
- Sur la seconde ligne, affichez $n$ entiers $c_1,c_2,\ldots,c_n$ ($1 \le c_i \le k$), où $c_i$ est la couleur que Mansur choisit pour le $i$-ème nombre du tableau. S'il existe plusieurs façons de colorier le tableau de manière optimale, affichez-en une quelconque.
Sous-tâches
Soit $S$ la somme de $n$ sur tous les cas de test.
| Sous-tâche | Contraintes supplémentaires | Points | Sous-tâches nécessaires |
|---|---|---|---|
| 0 | Exemple | 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 |
Exemples
Entrée 1
2 3 1 1 2 3 3 2 1 2 3
Sortie 1
1 1 1 1 3 1 1 2