E. Skibidus and Rizz
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

With the approach of Valentine's Day, Skibidus desperately needs a way to rizz up his crush! Fortunately, he knows of just the way: creating the perfect Binary String!

Given a binary string$$$^{\text{∗}}$$$ $$$t$$$, let $$$x$$$ represent the number of $$$\texttt{0}$$$ in $$$t$$$ and $$$y$$$ represent the number of $$$\texttt{1}$$$ in $$$t$$$. Its balance-value is defined as the value of $$$\max(x-y, y-x)$$$.

Skibidus gives you three integers $$$n$$$, $$$m$$$, and $$$k$$$. He asks for your help to construct a binary string $$$s$$$ of length $$$n+m$$$ with exactly $$$n$$$ $$$\texttt{0}$$$'s and $$$m$$$ $$$\texttt{1}$$$'s such that the maximum balance-value among all of its substrings$$$^{\text{†}}$$$ is exactly $$$k$$$. If it is not possible, output -1.

$$$^{\text{∗}}$$$A binary string only consists of characters $$$\texttt{0}$$$ and $$$\texttt{1}$$$.

$$$^{\text{†}}$$$A string $$$a$$$ is a substring of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by the deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

Input

The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The first and only line of each test case contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$0 \leq n, m \leq 2\cdot 10^5$$$, $$$1 \leq k \leq n + m$$$, $$$n+m\geq 1$$$).

It is guaranteed that the sum of $$$n$$$ and the sum of $$$m$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output

For each test case, if it is possible to construct $$$s$$$, output it on a new line. If there are multiple possible $$$s$$$, output any. Otherwise, output -1 on a new line.

Example
Input
6
1 2 1
4 3 2
2 4 3
8 3 2
5 0 4
5 0 5
Output
101
0100101
011011
-1
-1
00000
Note

In the first test case, we must construct $$$s$$$ such that it contains one $$$\texttt{0}$$$, two $$$\texttt{1}$$$, and a maximum balance of $$$1$$$ among all of its substrings. One possible valid $$$s$$$ is $$$\texttt{101}$$$ because:

  • Consider the substring bounded by indices $$$[1, 1]$$$. Its balance-value is $$$\max(0 - 1, 1 - 0) = 1$$$.
  • Consider the substring bounded by indices $$$[1, 2]$$$. Its balance-value is $$$\max(1 - 1, 1 - 1) = 0$$$.
  • Consider the substring bounded by indices $$$[1, 3]$$$. Its balance-value is $$$\max(1 - 2, 2 - 1) = 1$$$.
  • Consider the substring bounded by indices $$$[2, 2]$$$. Its balance-value is $$$\max(1 - 0, 0 - 1) = 1$$$.
  • Consider the substring bounded by indices $$$[2, 3]$$$. Its balance-value is $$$\max(1 - 1, 1 - 1) = 0$$$.
  • Consider the substring bounded by indices $$$[3, 3]$$$. Its balance-value is $$$\max(0 - 1, 1 - 0) = 1$$$.

Among all possible substrings, the maximum balance-value is $$$1$$$.

In the second test case, the substring with the maximum balance-value is $$$0100$$$, which has a balance of $$$max(3-1, 1-3)=2$$$.