← 返回题目列表

Codeforces · 1400/C

C. 二进制字符串重建

中文机器翻译题面 查看原题

考虑以下过程。您有一个长度为 $$$n$$$ 的二进制字符串(每个字符为 0 或 1 的字符串)$$$w$$$ 和一个整数 $$$x$$$。您构建一个由 $$$n$$$ 字符组成的新二进制字符串 $$$s$$$。 $$$s$$$ 的第 $$$i$$$ 个字符选择如下:

- 如果字符 $$$w_{i-x}$$$ 存在并且等于 1,则 $$$s_i$$$ 为 1(正式来说,如果 $$$i > x$$$ 且 $$$w_{i-x} = $$$ 1,则 $$$s_i = $$$ 1);
- 如果字符 $$$w_{i+x}$$$ 存在并且等于 1,则 $$$s_i$$$ 为 1(正式来说,如果 $$$i + x \le n$$$ 且 $$$w_{i+x} = $$$ 1,则 $$$s_i = $$$ 1);
- 如果上述两个条件均为假,则 $$$s_i$$$ 为 0。

给定整数 $$$x$$$ 和结果字符串 $$$s$$$。重建原始字符串$$$w$$$。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。

每个测试用例由两行组成。第一行包含结果字符串 $$$s$$$ ($$$2 \le |s| \le 10^5$$$,$$$s$$$ 的每个字符不是 0 就是 1)。第二行包含一个整数 $$$x$$$ ($$$1 \le x \le |s| - 1$$$)。

输入中所有字符串$$$s$$$的总长度不超过$$$10^5$$$。

输出

对于每个测试用例,将答案打印在单独的行上,如下所示:

- 如果在进程结束时没有字符串 $$$w$$$ 可以生成字符串 $$$s$$$,则打印 $$$-1$$$;
- 否则,打印由 $$$|s|$$$ 字符组成的二进制字符串 $$$w$$$。如果有多个答案,请打印其中任何一个。

示例

输入 #1

3
101110
2
01
1
110
1

输出 #1

111011
10
-1