题目描述

情人节将至，Skibidus 拼命需要一种方法来吸引他的暗恋对象！幸运的是，他找到了正解：制造完美的二进制字符串！

给定一个二进制字符串$^{\text{∗}}$ $t$，令 $x$ 表示 $t$ 中 $\texttt{0}$ 的个数，$y$ 表示 $t$ 中 $\texttt{1}$ 的个数。我们定义字符串的平衡值为 $\max(x-y,\, y-x)$。

Skibidus 给你三个整数 $n$，$m$ 和 $k$。他希望你构造一个长度为 $n+m$ 的二进制字符串 $s$，其中恰好包含 $n$ 个 $\texttt{0}$ 和 $m$ 个 $\texttt{1}$，并且要求其所有子串$^{\text{†}}$的平衡值的最大值恰好为 $k$。如果不存在满足条件的字符串，请输出 -1。

$^{\text{∗}}$ 二进制字符串指仅由字符 $\texttt{0}$ 和 $\texttt{1}$ 组成的字符串。

$^{\text{†}}$ 字符串 $a$ 是字符串 $b$ 的子串，意味着 $a$ 可以通过删除 $b$ 开头和结尾的若干（可能为 0 或全部）字符得到。

输入格式

第一行包含一个整数 $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$，输出任意一个满足条件的字符串；否则，输出 -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$，包含 1 个 $\texttt{0}$ 和 2 个 $\texttt{1}$，且所有子串中的最大平衡值为 $1$。一个可能的满足条件的字符串是 $\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$。

在第二个测试用例中，具有最大平衡值的子串为 $\texttt{0100}$，其平衡值为 $\max(3-1,\, 1-3) = 2$。

来源

Codeforces 2065E，英文题名 Skibidus and Rizz。