408446: GYM103119 C Club Assignment

There are $$$n$$$ freshmen who failed to join any club, they decided to set up two new clubs by themselves. It is encouraged to make more new friends in the club, so they want an extreme "random" partition result.

Formally, the personality of the $$$i$$$-th freshman can be represented as a positive integer $$$w_i$$$, the similarity between two freshmen $$$A$$$ and $$$B$$$ can be measured as $$$w_A\oplus w_B$$$, where "$$$\oplus$$$" denotes the bitwise xor operation. Your task is to assign each freshman to either the new club $$$1$$$ or the new club $$$2$$$, such that the smallest value of similarity between two freshmen in the same club is maximized.

The input contains multiple cases. The first line of the input contains a single integer $$$T$$$ ($$$1 \leq T \leq 10\,000$$$), the number of cases.

For each case, the first line of the input contains an integer $$$n$$$ ($$$3 \leq n \leq 100\,000$$$), denoting the number of freshmen.

The second line contains $$$n$$$ integers $$$w_1,w_2,\dots,w_n$$$ ($$$1\le i \le n,\ 1 \leq w_i\leq 10^9$$$), denoting the personality of each freshman.

It is guaranteed that the sum of $$$n$$$ over all cases does not exceed $$$200\,000$$$.

For each case, print two lines. Print a single integer in the first line, denoting the smallest value of similarity between two freshmen in the same club in your solution. Then print $$$n$$$ digits in the second line, denoting the solution you find. If the $$$i$$$-th freshman is assigned to the first club, the $$$i$$$-th digit should be '1', and if the $$$i$$$-th freshman is assigned to the second club, the $$$i$$$-th digit should be '2'.

If there is more than one solution, any one of them will be accepted.

2
3
1 2 3
3
5 5 5

3
112
0
122