CF1400C Binary String Reconstruction

考虑如下过程。你有一个长度为 $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$。如果有多种答案，输出其中任意一种即可。

由 ChatGPT 4.1 翻译