Description

Little A has $n$ powers of $2$, $a_1, a_2, \cdots, a_n$. He wants to insert $x$ XOR operators and $y$ OR operators between these numbers to form an expression. It is guaranteed that $x + y = n - 1$.

The larger the expression is, the more likely it can blow up Little T's blog. Little A wants the value of the expression to be as large as possible when it is evaluated from left to right. He wants to know the maximum possible value of the expression, written in binary. He also wants you to construct such an expression, because he is too lazy to do it himself.

If there are multiple valid constructions, output any one.

There are multiple test cases.

Input Format

The first line contains an integer $S$, the index of the subtask.

The second line contains an integer $T$, the number of test cases. Then follow $T$ test cases, each in the following form:

• The first line contains three integers $n, x, y$.
• The second line contains $n$ integers $b_i$, meaning $a_i = 2 ^ {b_i}$.

Output Format

For each test case:

• The first line outputs a binary number representing the answer. Leading zeros are not allowed, unless the answer is $0$.
• The second line outputs a string of length $n - 1$ consisting of ^ and |, where $s_i = \texttt{\,\,\^{}\,\,}$ means the operator between $a_i$ and $a_{i + 1}$ is XOR, and $s_i = \texttt |$ means the operator is OR. You must ensure that the number of ^ is $x$ and the number of | is $y$.

0
4
4 0 3
1 0 6 4
8 5 2
1 5 5 7 1 5 5 7
1 0 0
15
4 3 0
65535 65535 57 57

1010011
|||
10100000
^|^^^^|
1000000000000000

0
^^^

Hint

"Scoring"

For each test case:

• If the first line you output is worse than the standard answer, you get 0 points.
• If the first line you output is better than the standard answer, then the checker will verify whether your construction is correct. If it is correct, it returns _fail, which appears as UKE for the test point; otherwise you get 0 points.
• Otherwise, your first line is the same as the standard answer. If your construction is incorrect, you get 0.6 points; otherwise you get 1 point.

The score of each test point is the minimum score among all test cases in that test point multiplied by the value of that test point.

Note that the checker can detect that your answer is better than the standard answer only if your output strictly matches the format. Once the output format is incorrect, you get 0 points. Format restrictions include but are not limited to:

• In the first line, you must not output characters other than 0 and 1.
• In the second line, you must not output characters other than ^ and |, and the string length must be exactly $n - 1$.
• The number of ^ must be exactly $x$, and the number of | must be exactly $y$.

"Constraints and Conventions"

• Test point #1 (10 points): all $b_i$ are pairwise distinct.
• Test point #2 (20 points): all $b_i$ are equal.
• Test point #3 (30 points): $n \leq 8$.
• Test point #4 (25 points): $n \leq 10 ^ 3$.
• Test point #5 (15 points): no special restrictions.

For $100\%$ of the data:

• $1\leq T\leq 20$.
• $1 \leq n \leq 2.5 \times 10 ^ 4$.
• $0 \leq x, y < n$, $x + y = n - 1$.
• $1\leq a_i < 2 ^ {2 ^ {2 ^ {2 ^ 2}}}$, i.e. $0\leq b_i < 65536$.

"Help and Tips"

• About bit operations。
• Please pay attention to IO optimization.

"Source"

• Sweet Round 8 B
• Idea & Solution: Alex_Wei。
• Tester: chenxia25。

Translated by ChatGPT 5