Binary String Reconstruction

题意翻译

给出一种01串的变换方法及对一个串变换后的结果串，求出原串（可以有多种），多组询问。 变换方法如下： 原串为 $w$，变换后的串为 $s$，两串长度相等；给出一个整数 $x$；01串从下标 $1$ 开始。 - 如果原串 $w_{i-x}$ 这一位存在且为 $\mathbf{1}$，那么 $s_i$ 为 $\mathbf1$（形式化地说，如果 $i\gt x$ 且 $w_{i-x}=\mathbf1$，那么 $s_i=\mathbf1$）。 - 如果原串 $w_{i+x}$ 这一位存在且为 $\mathbf{1}$，那么 $s_i$ 为 $\mathbf1$（形式化地说，如果 $i+ x\le n$ 且 $w_{i+x}=\mathbf1$，那么 $s_i=\mathbf1$）。 - 如果上述两种情况均不成立，那么 $s_i=\mathbf0$。 给出 $s$，求出一种可能的 $w$，若不存在任意一种 $w$，输出`-1`。 保证 $s$ 的总长度不超过 $10^5$，$t$（数据组数）不超过 $1000$。

题目描述

Consider the following process. You have a binary string (a string where each character is either 0 or 1) $ w $ of length $ n $ and an integer $ x $ . You build a new binary string $ s $ consisting of $ n $ characters. The $ i $ -th character of $ s $ is chosen as follows: - if the character $ w_{i-x} $ exists and is equal to 1, then $ s_i $ is 1 (formally, if $ i > x $ and $ w_{i-x} = $ 1, then $ s_i = $ 1); - if the character $ w_{i+x} $ exists and is equal to 1, then $ s_i $ is 1 (formally, if $ i + x \le n $ and $ w_{i+x} = $ 1, then $ s_i = $ 1); - if both of the aforementioned conditions are false, then $ s_i $ is 0. You are given the integer $ x $ and the resulting string $ s $ . Reconstruct the original string $ w $ .

输入输出格式

输入格式

The first line contains one integer $ t $ ( $ 1 \le t \le 1000 $ ) — the number of test cases. Each test case consists of two lines. The first line contains the resulting string $ s $ ( $ 2 \le |s| \le 10^5 $ , each character of $ s $ is either 0 or 1). The second line contains one integer $ x $ ( $ 1 \le x \le |s| - 1 $ ). The total length of all strings $ s $ in the input does not exceed $ 10^5 $ .

输出格式

For each test case, print the answer on a separate line as follows: - if no string $ w $ can produce the string $ s $ at the end of the process, print $ -1 $ ; - otherwise, print the binary string $ w $ consisting of $ |s| $ characters. If there are multiple answers, print any of them.

输入输出样例

输入样例 #1

3
101110
2
01
1
110
1

输出样例 #1

111011
10
-1