{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eThere 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.\u003c/p\u003e\u003cp\u003eFormally, 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.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe 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.\u003c/p\u003e\u003cp\u003eFor each case, the first line of the input contains an integer $$$n$$$ ($$$3 \\leq n \\leq 100\\,000$$$), denoting the number of freshmen.\u003c/p\u003e\u003cp\u003eThe 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.\u003c/p\u003e\u003cp\u003eIt is guaranteed that the sum of $$$n$$$ over all cases does not exceed $$$200\\,000$$$.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor 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 \u0027\u003cspan class\u003d\"tex-font-style-tt\"\u003e1\u003c/span\u003e\u0027, and if the $$$i$$$-th freshman is assigned to the second club, the $$$i$$$-th digit should be \u0027\u003cspan class\u003d\"tex-font-style-tt\"\u003e2\u003c/span\u003e\u0027.\u003c/p\u003e\u003cp\u003eIf there is more than one solution, any one of them will be accepted.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\n3\n1 2 3\n3\n5 5 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\n112\n0\n122\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}