{"problem":{"name":"[ICPC 2022 Xi'an R] Power of Two","description":{"content":"$$ 2 ^ {2 ^ {2 ^ {2 ^ {2 ^ {2 ^ {2 ^ {2 ^ {2 ^ {2}}}}}}}}} $$ SolarPea likes blowing up PolarSea's blog by sending power tower of $2$. As the tower is too high, the stack of the web page overflows. S","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9365"},"statements":[{"statement_type":"Markdown","content":"$$\n2 ^ {2 ^ {2 ^ {2 ^ {2 ^ {2 ^ {2 ^ {2 ^ {2 ^ {2}}}}}}}}}\n$$\n\nSolarPea likes blowing up PolarSea's blog by sending power tower of $2$. As the tower is too high, the stack of the web page overflows. So the blog no longer works.\n\nNow SolarPea has $n$ powers of two $a_1, a_2, \\ldots, a_n$, $x$ bitwise AND operators, $y$ bitwise OR operators and $z$ bitwise XOR operators. It is guaranteed that $n = x + y + z$.\n\nSolarpea wants to construct an arithmetic expression with these numbers and operators. Formally, define $x_0 = 0$ and $x_i = x_{i - 1}\\ \\mathrm{op}_i\\ b_i$, where $b$ is a permutation of $a$, which means we can rearrange $a$ to get $b$, and $\\mathrm{op}_i$ is one of the three types of bitwise operators above. Then $x_n$ is the result of the expresstion.\n\nThe larger the expression, the more likely it is to make PolarSea's blog unable to work. SolarPea wants you to help him to find the largest $x_n$ and construct such an expression. If there are multiple solutions, output any of them.\n\nYou need to process $T$ test cases independently.\n\n## Input\n\nThe first line contains a single integer $T$ ($1\\leq T \\leq 10 ^ 5$), denoting the number of test cases.\n\nFor each test case, the first line contains four integers $n$, $x$, $y$ and $z$ ($0\\leq x, y, z\\leq n \\leq 65\\,536, n = x + y + z$). The next line contains $n$ integers $c_1, c_2, \\ldots, c_n$ ($0\\leq c_i < n$), where $a_i = 2 ^ {c_i}$.\n\nIt is guaranteed that the sum of $n$ over all test cases is no more than $1\\,048\\,576$.\n\n## Output\n\nFor each test case, output three lines.\n\nThe first line contains a $01$-string of length $n$, representing the binary form of the largest $x_n$.\n\nThe next line contains a single $1$-indexed string $\\mathrm{op}$ of length $n$, where $\\mathrm{op}_i$ represents the $i$-th operator. Here, we denote AND as `&` (ASCII 38), OR as `|` (ASCII 124), and XOR as `^` (ASCII 94). You should guarantee that there is exactly $x$ AND operators, $y$ OR operators and $z$ XOR operators.\n\nThe third line contains $n$ integers $d_1, d_2, \\ldots, d_n$, the $i$-th of which representing the logarithm of $b_i$ with base $2$. That is, $d$ is a permutaion of $c$.\n\nIf there are multiple solutions, output any of them.\n\n[samples]\n\n## Note\n\n**Source**: The 2022 ICPC Asia Xi'an Regional Contest Problem H.\n\n**Author**: Alex_Wei.\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/g2frgx9s.png)","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9365","tags":["2022","Special Judge","O2优化","构造","ICPC","分类讨论","西安"],"sample_group":[["4\n4 3 0 1\n1 0 1 0\n4 1 0 3\n1 0 1 0\n8 0 2 6\n1 5 5 7 1 5 5 7\n8 0 0 8\n1 5 5 7 1 5 5 7\n","0010\n&&^&\n0 0 1 1\n0011\n^^&^\n0 1 0 1\n10100000\n^^|^^^^|\n1 5 5 7 1 5 5 7\n00000000\n^^^^^^^^\n1 5 5 7 1 5 5 7\n"]],"created_at":"2026-03-03 11:09:25"}}