С приближением Дня Святого Валентина Скибидус отчаянно нуждается в способе привлечь внимание своей возлюбленной! К счастью, он знает, как это сделать: создать идеальную двоичную строку!
Дана двоичная строка\(^{\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.
Выходные данные
Для каждого набора входных данных, если возможно построить строку \(s\), выведите её на новой строке. Если существует несколько возможных строк \(s\), выведите любую. В противном случае выведите -1 на новой строке.
Примечание
В первом примере мы должны построить \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
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
|