A. A + B = C Problem
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Given three positive integers $$$p_A,p_B,p_C$$$, Bobo challenges you to find out three infinite binary strings $$$A,B,C$$$ with period $$$p_A$$$, $$$p_B$$$ and $$$p_C$$$ respectively satisfying $$$A \oplus B = C$$$, or determine it is impossible to do so.

Please refer to the Note section for the formal definition of period and exclusive or.

Input

The first line of the input contains a single integer $$$T$$$ ($$$1 \le T \le 10^4$$$), denoting the number of test cases. The description of the test cases follows.

The first and the only line of each test case contains three integers $$$p_A$$$, $$$p_B$$$ and $$$p_C$$$ ($$$1 \le p_A,p_B,p_C \le 10^6$$$).

It is guaranteed that the sum of $$$\max(p_A,p_B,p_C)$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, output "NO" (without quotes) in one line if no solution exists. Otherwise, output "YES" (without quotes) in one line. Then, output three binary strings of length $$$p_A$$$, $$$p_B$$$ and $$$p_C$$$ in three lines, denoting the first $$$p_A$$$, $$$p_B$$$, $$$p_C$$$ character(s) of the infinite strings $$$A$$$, $$$B$$$, $$$C$$$ respectively.

You can output "YES" and "NO" in any case (for example, strings "yES", "yes", and "Yes" will all be recognized as a positive response).

Example
Input
2
2 3 6
2 3 5
Output
YES
01
011
001110
NO
Note

Let $$$s=s_1 s_2 s_3 \ldots$$$ and $$$t=t_1 t_2 t_3 \ldots$$$ be infinite binary strings.

The period of $$$s$$$ is the smallest positive integer $$$k$$$ satisfying $$$s_i = s_{i+k}$$$ for all $$$i \ge 1$$$.

The exclusive or of strings $$$s$$$ and $$$t$$$ is given by $$$s \oplus t$$$ satisfying $$$(s \oplus t)_i = s_i \oplus t_i$$$ for all $$$i \ge 1$$$.