#LUOGUP9021. Maps.

    ID: 1248 远端评测题 1000ms 512MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>贪心洛谷原创O2优化构造洛谷月赛

Maps.

题目描述

小 Y 希望得到一幅地图,这份地图有些与众不同。

这份地图是一幅长为 nn 个单位,宽为一个单位的网格图,每个网格必须被涂鸦成白色(00)或者黑色(11)。

你希望满足小 Y 的愿望送给他一幅这样的地图,但是这时小 Y 又提出了两点要求:

  • 对于每个不在网格图两端的白色格子,恰好有 pp 个满足它的左右两个格子都被涂鸦成黑色。
  • 在满足上述所有条件的情况下,这幅地图从左到右的字符构成的字符串的字典序最小。

你心想,这些要求也是小菜一碟,于是开始了你的创作。

输入格式

本题有多组数据。

第一行一个正整数 TT,表示数据组数。

对于每组数据:

输入共一行两个整数 n,pn,p,表示你需要构造的地图的长度和小 Y 对你的要求。

输出格式

对于每组数据:输出一行一个长度为 nn 的 01 字符串,表示你构造的地图;如果无法找到任何一幅地图满足小 Y 的要求,输出 1-1

5
5 1
3 1
5 3
5 4
5 5
00101
101
-1
-1
-1

提示

【样例解释 #1】

对于第一组数据:只有位于第 44 个字符上的数,满足本身是 00,不在地图边缘且周围两个都是 11,因此符合条件。可以证明这是满足条件的字典序最小的方案。

对于第三组数据:可以证明没有任何一个解满足长度为 55 且有 33 个数本身是 00,不在地图边缘且周围两个字符都是 11

【数据范围】

对于所有测试数据,满足 1T1001 \le T \le 1001n,p1051 \le n,p \le 10^5

本题开启捆绑测试,所有数据范围均相同的测试点捆绑为一个 Subtask\text{Subtask}

各测试点的附加限制如下表所示。

测试点 n,pn,p \le
131 \sim 3 1010
454 \sim 5 10310^3
6106\sim 10 10510^5