小 Y 希望得到一幅地图,这份地图有些与众不同。
这份地图是一幅长为 n 个单位,宽为 1 个单位的网格图,每个网格必须被涂鸦成白色( 0 )或者黑色( 1 )。
你希望满足小 Y 的愿望送给他一幅这样的地图,但是这时小 Y 又提出了两点要求:
你心想,这些要求也是小菜一碟,于是开始了你的创作。
本题有多组数据。
第一行一个正整数 T ,表示数据组数。
对于每组数据:
输入共一行两个整数 n,p ,表示你需要构造的地图的长度和小 Y 对你的要求。
对于每组数据:输出一行一个长度为 n 的 01 字符串,表示你构造的地图;
如果无法找到任何一幅地图满足小 Y 的要求,输出 -1 。
5 5 1 3 1 5 3 5 4 5 5
00101 101 -1 -1 -1
对于第一组数据:只有位于第 4 个字符上的数,满足本身是 0 ,不在地图边缘且周围两个都是 1 ,因此符合条件。
可以证明这是满足条件的字典序最小的方案。
对于第三组数据:可以证明没有任何一个解满足长度为 5 且有 3 个数本身是 0 ,不在地图边缘且周围两个字符都是 1 。
对于所有测试数据,满足 1 \le T \le 100 , 1 \le n,p \le 10^5 。
各测试点的附加限制如下表所示。
P9687 Maps.