Tima ist von seiner Reise nach Xorland zurückgekehrt und hat ein Array aus $n$ ganzen Zahlen mitgebracht. Xorland ist ein kleines Land, das für sein Essen, seine Musik und seine Spiele mit Arrays bekannt ist. Eine Besonderheit dieser Spiele ist, dass es keinen Sieger gibt: Die Freundschaft gewinnt immer! Eines dieser Spiele heißt „Xor-Mat“.
Die Regeln von „Xor-Mat“ sind einfach. Vor Spielbeginn wählen zwei Spieler ein Array $a$ und eine ganze Zahl $k$. Dann färbt der erste Spieler jede Zahl im Array mit einer von $k$ Farben. Wenn die Farben von $1$ bis $k$ nummeriert sind, sei $c_i$ die Farbe der $i$-ten Zahl im Array. Anschließend wählt der zweite Spieler ein Indexpaar $(i,j)$ mit $i\ne j$ und $c_i=c_j$.
Der erste Spieler möchte $a_i\oplus a_j$ maximieren, während der zweite Spieler $a_i\oplus a_j$ minimieren möchte. Dabei bezeichnet $\oplus$ das bitweise „XOR“.
Mansur hat Tima zu einer Partie „Xor-Mat“ herausgefordert. Sie spielen mit Timas Array. Mansur spielt zuerst, Tima als Zweiter. Gib den Wert von $a_i\oplus a_j$ aus, wenn beide Spieler optimal spielen. Bestimme außerdem eine optimale Färbung des Arrays, die Mansur wählen könnte.
Eingabe
Die erste Zeile enthält eine ganze Zahl $t$ ($1\le t\le 5\cdot 10^4$), die Anzahl der Testfälle.
Es folgen $2\cdot t$ Zeilen nach folgendem Muster:
Die erste Zeile jedes Testfalls enthält zwei ganze Zahlen $n$ ($2\le n\le 5\cdot 10^4$) und $k$ ($1\le k\le \min(n-1,50)$).
Die zweite Zeile jedes Testfalls enthält $n$ ganze Zahlen $a_1,a_2,\ldots,a_n$ ($1\le a_i\le 10^9$), Timas Array.
Es ist garantiert, dass die Summe von $n$ über alle Testfälle $5\cdot 10^4$ nicht überschreitet.
Ausgabe
Gib für jeden Testfall zwei Zeilen aus:
- Gib in der ersten Zeile den Wert von $a_i\oplus a_j$ aus, wenn beide Spieler optimal spielen.
- Gib in der zweiten Zeile $n$ ganze Zahlen $c_1,c_2,\ldots,c_n$ ($1\le c_i\le k$) aus, wobei $c_i$ die Farbe ist, die Mansur für die $i$-te Zahl des Arrays wählt. Falls mehrere optimale Färbungen möglich sind, gib eine beliebige davon aus.
Teilaufgaben
Sei $S$ die Summe von $n$ über alle Testfälle.
| Teilaufgabe | Zusätzliche Beschränkungen | Punkte | Erforderliche Teilaufgaben |
|---|---|---|---|
| 0 | Beispiel | 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 |
Beispiele
Eingabe 1
2 3 1 1 2 3 3 2 1 2 3
Ausgabe 1
1 1 1 1 3 1 1 2