E. Скибидус и rizz
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

С приближением Дня Святого Валентина Скибидус отчаянно нуждается в способе привлечь внимание своей возлюбленной! К счастью, он знает, как это сделать: создать идеальную двоичную строку!

Дана двоичная строка$$$^{\text{∗}}$$$ $$$t$$$, пусть $$$x$$$ представляет количество $$$\texttt{0}$$$ в $$$t$$$, а $$$y$$$ представляет количество $$$\texttt{1}$$$ в $$$t$$$. Тогда её баланс определяется как значение $$$\max(x-y, y-x)$$$.

Скибидус дает вам три целых числа $$$n$$$, $$$m$$$ и $$$k$$$. Он просит вас помочь ему построить двоичную строку $$$s$$$ длиной $$$n+m$$$ из ровно $$$n$$$ символов $$$\texttt{0}$$$ и $$$m$$$ символов $$$\texttt{1}$$$, так что максимальный баланс среди всех её подстрок$$$^{\text{†}}$$$ равен ровно $$$k$$$. Если это невозможно, выведите -1.

$$$^{\text{∗}}$$$Двоичная строка состоит только из символов $$$\texttt{0}$$$ и $$$\texttt{1}$$$.

$$$^{\text{†}}$$$Строка $$$a$$$ является подстрокой строки $$$b$$$, если $$$a$$$ может быть получена из $$$b$$$ путем удаления нескольких (возможно, нуля или всех) символов с начала и нескольких (возможно, нуля или всех) символов с конца.

Входные данные

Первая строка содержит целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных.

Первая и единственная строка каждого набора содержит три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$0 \leq n, m \leq 2\cdot 10^5$$$, $$$1 \leq k \leq n + m$$$, $$$n+m\geq 1$$$).

Гарантируется, что сумма $$$n$$$ и сумма $$$m$$$ по всем наборам входных данных не превышают $$$2\cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных, если возможно построить строку $$$s$$$, выведите её на новой строке. Если существует несколько возможных строк $$$s$$$, выведите любую. В противном случае выведите -1 на новой строке.

Пример
Входные данные
6
1 2 1
4 3 2
2 4 3
8 3 2
5 0 4
5 0 5
Выходные данные
101
0100101
011011
-1
-1
00000
Примечание

В первом примере мы должны построить $$$s$$$ так, чтобы он содержал одну $$$\texttt{0}$$$, две $$$\texttt{1}$$$ и максимальный баланс $$$1$$$ среди всех её подстрок. Одним из возможных корректных $$$s$$$ является $$$\texttt{101}$$$, потому что:

  • Рассмотрим подстроку, ограниченную индексами $$$[1, 1]$$$. Её баланс равен $$$\max(0 - 1, 1 - 0) = 1$$$.
  • Рассмотрим подстроку, ограниченную индексами $$$[1, 2]$$$. Её баланс равен $$$\max(1 - 1, 1 - 1) = 0$$$.
  • Рассмотрим подстроку, ограниченную индексами $$$[1, 3]$$$. Её баланс равен $$$\max(1 - 2, 2 - 1) = 1$$$.
  • Рассмотрим подстроку, ограниченную индексами $$$[2, 2]$$$. Её баланс равен $$$\max(1 - 0, 0 - 1) = 1$$$.
  • Рассмотрим подстроку, ограниченную индексами $$$[2, 3]$$$. Её баланс равен $$$\max(1 - 1, 1 - 1) = 0$$$.
  • Рассмотрим подстроку, ограниченную индексами $$$[3, 3]$$$. Её баланс равен $$$\max(0 - 1, 1 - 0) = 1$$$.

Среди всех возможных подстрок максимальный баланс равен $$$1$$$.

Во втором примере подстрока с максимальным балансом — это $$$0100$$$, которая имеет баланс $$$max(3-1, 1-3)=2$$$.