Maximizing Left-to-Right Bitwise Expression

We are given n numbers, each of which is a power of 2: a₁, a₂, …, a_n. You must insert exactly x XOR operators (^) and y OR operators (|) between them (so that x+y = n-1) to form an expression. The expression is evaluated from left to right (i.e. no conventional operator precedence).

The goal is to maximize the final value of the expression. Let the computed value be V. You must output V in its binary representation, and also produce one valid operator‐assignment so that the value is maximized. If there are multiple valid solutions, you may output any one of them.

Note on evaluation: Suppose you have the partial value R and then you perform an operation with the next number a. If the operator is OR (|) then the new value is R | a. If the operator is XOR (^) then the new value is R ^ a. Since each a_i is a power of 2 (i.e. has exactly one binary bit set), the effect of each operator on each bit is simple. In particular, if a bit is set in the result then OR-ing with a same-power-of-2 will leave it set, while XOR-ing will toggle that particular bit. In order to maximize the final result (which is equivalent to obtaining the bitwise OR of all a_i if possible), you must decide where you can “waste” XOR’s if forced to use them.

Task: Given the numbers and exactly x XOR and y OR operators (with x+y = n-1), choose an assignment for the operators that maximizes the final value when evaluated sequentially. Output that maximum value (in binary) and a valid expression achieving it.

Input format (multiple test cases):
The first line contains an integer T, the number of test cases. Each test case consists of two lines. The first line contains three integers: n, x, y, with x+y = n-1. The second line contains n space‐separated integers a₁, a₂, …, a_n, each of which is a power of 2.

Output format:
For each test case, output two lines. The first line is the maximum possible value (in binary, without any prefix). The second line is an expression in the format:

a1 op1 a2 op2 a3 ... op(n-1) an

where each op is either ^ or |, corresponding to the chosen insertion. The expression must evaluate (left-to-right) to the maximum possible value.

inputFormat

The input begins with an integer T (T ≥ 1) denoting the number of test cases. Each test case consists of two lines:

• The first line contains three integers n, x, and y (with x + y = n - 1).
• The second line contains n integers: a₁, a₂, …, a_n. Each a_i is a power of 2.

outputFormat

For each test case, output two lines:

• The first line is the maximum value achievable, represented in binary (without a prefix, e.g. no '0b').
• The second line is a valid expression (with spaces separating numbers and operators) that yields this maximum value when evaluated from left to right. Operators must be either '^' (XOR) or '|' (OR).

sample

2
2 0 1
1 1
3 1 1
1 2 4

1
1 | 1
7
1 ^ 2 | 4