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$.


-----Input-----

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$.


-----Output-----

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. 


-----Example-----
Input
3
101110
2
01
1
110
1

Output
111011
10
-1

Difficulty: interview

Starter code:

Solutions:
import sys

input=sys.stdin.readline

for _ in range(int(input())):
    s=input().rstrip()
    x=int(input())
    n=len(s)
    ans=["1" for i in range(n)]
    for i in range(n):
        if s[i]=="0":
            if i-x>=0:
                ans[i-x]="0"
            if i+x<n:
                ans[i+x]="0"
    for i in range(n):
        if s[i]=="1":
            check=False
            if i-x>=0:
                check|=(ans[i-x]=="1")
            if i+x<n:
                check|=(ans[i+x]=="1")
            if not check:
                print(-1)
                break
    else:
        print("".join(ans))


import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    s = input().strip()
    n = len(s)
    x = int(input())
    outl = ['1'] * n
    for i in range(n):
        if s[i] == '0':
            if i >= x:
                outl[i-x] = '0'
            if i + x < n:
                outl[i+x] = '0'
    out = ''.join(outl)
    works = True
    for i in range(n):
        if s[i] == '1':
            if (i < x or out[i - x] == '0') and (i + x >= n or out[i + x] == '0'):
                works = False
                break

    if works:
        print(out)
    else:
        print(-1)


t = int(input())
for _ in range(t):
    s = input()
    n = len(s)
    x = int(input())
    w = [0]*n
    for i in range(n):
        if 0 <= i + x < n and 0 <= i - x < n:
            if s[i+x] == "1" and s[i-x] == "1":
                w[i] = 1
        elif 0 <= i + x < n:
            if s[i+x] == "1":
                w[i] = 1
        elif 0 <= i - x < n:
            if s[i-x] == "1":
                w[i] = 1

    for i in range(n):
        if 0 <= i-x < n and w[i-x] == 1:
            if s[i] == "1":
                continue
            else:
                print(-1)
                break
        if 0 <= i + x < n and w[i+x] == 1:
            if s[i] == "1":
                continue
            else:
                print(-1)
                break
        if s[i] == "1":
            print(-1)
            break
    else:
        print(*w, sep="")




def process():
    li=list(input())
    x=int(input())
    n=len(li)
    ans=['1' for i in range(n)]

    for i in range(0,n):
        if(li[i]=='0'):
            if(i-x>=0):
                ans[i-x]='0'
            if(i+x<n):
                ans[i+x]='0'

    for i in range(0,n):
        chr='0'
        if(i-x>=0 and ans[i-x]=='1'):
            chr='1'
        if(i+x<n and ans[i+x]=='1'):
            chr='1'
        if(li[i]==chr):
            pass
        else:
            print(-1)
            return
    print("".join(ans))



tests=int(input())
for i in range(tests):
    process()

import sys
# sys.stdin = open('input.txt', 'r') 
# sys.stdout = open('output.txt', 'w')
 
import math
import collections
from sys import stdin,stdout,setrecursionlimit
import bisect as bs
setrecursionlimit(2**20)
M = 10**9+7
    
T = int(stdin.readline())
# T = 1

for _ in range(T):
    # n = int(stdin.readline())
    # n,d,m = list(map(int,stdin.readline().split()))
    # a = list(map(int,stdin.readline().split()))
    # q = int(stdin.readline())
    # a = list(map(int,stdin.readline().split()))
    # b = list(map(int,stdin.readline().split()))
    s = stdin.readline().strip('\n')
    x = int(stdin.readline())
    n = len(s)
    a = [-1]*n
    res = True
    for i in range(n):
        if(s[i] == '1'):
            if((i-x) >= 0 and a[i-x] != 0):
                a[i-x] = 1
                continue
            if((i+x) < n):
                if(a[i+x] == 0):
                    res = False
                    break
                else:
                    a[i+x] = 1
                    continue
            res = False
            break
        else:
            if((i-x) >= 0):
                if(a[i-x] == 1):
                    res = False
                    break
                else:
                    a[i-x] = 0
            if((i+x) < n):
                if(a[i+x] == 1):
                    res = False
                    break
                else:
                    a[i+x] = 0
    ans = ''
    for i in range(n):
        if(a[i] != -1):
            ans = ans + str(a[i])
        else:
            ans = ans + '1'
    if(res): print(ans)
    else: print(-1)


from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop,heapify
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

from itertools import accumulate

M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]



for _ in range(val()):
    l = [0] + li3()
    x = val()
    n = len(l) - 1
    ans = [None] * (n + 1)
    flag = 0

    # print(l, n, x)
    for i in range(1, n + 1):
        # print(ans, i)
        if l[i] == 1:
            if i > x and (ans[i - x] == 1 or ans[i - x] == None):
                ans[i - x] = 1
            elif i + x <= n:
                ans[i + x] = 1
            else:
                flag = 1
                break
        else:
            if (i <= x or (ans[i - x] == None or ans[i - x ] == 0)) and (i + x > n or (ans[i + x] == None)):
                if i > x:ans[i - x] = 0
                if i + x <= n:ans[i + x] = 0
            else:
                flag = 1
                break
    for i in range(1, n + 1):
        if ans[i] == None:ans[i] = 1  
    if flag:
        print(-1)
    else:
        print(*ans[1:n + 1], sep = '')

for t in range(int(input())):
    s = [int(c == "1") for c in input()]
    x = int(input())
    n = len(s)

    sat = lambda i: (s[i] if i in range(n) else 1)

    w = [(sat(i - x) & sat(i + x)) for i in range(n)]

    wat = lambda i: (w[i] if i in range(n) else 0)

    s_ref = [(wat(i - x) | wat(i + x)) for i in range(n)]
    
    if s != s_ref:
        print(-1)
    else:
        print("".join(map(str, w)))


def solve():
    s = list(map(int, input()))
    n = len(s)
    x = int(input())
    w = [0] * n
    d = [False] * n
    for i in range(n):
        if s[i] == 0:
            if i - x >= 0:
                w[i - x] = 0
                d[i - x] = True
            if i + x < n:
                w[i + x] = 0
                d[i + x] = True
    for i in range(n):
        if not d[i]:
            w[i] = 1
            d[i] = True
    t = [0] * n
    for i in range(n):
        if i - x >= 0 and w[i - x] == 1:
            t[i] = 1
        if i + x < n and w[i + x] == 1:
            t[i] = 1
    if s != t:
        print('-1')
        return
    print(''.join(map(str, w)))
t = int(input())
for _ in range(t):
    solve()

t = int(input())
for i in range(t):
    s = input()
    m = len(s)
    x = int(input())
    ANS = [1] * m
    for i in range(m):
        if s[i] == "0":
            if i-x >= 0:
                ANS[i-x] = 0
            if i+x < m:
                ANS[i+x] = 0
    
    ng = 0
    for i in range(m):
        one = 0
        if (i-x >= 0 and ANS[i-x] == 1) or (i+x < m and ANS[i+x] == 1):
            one = 1
        if (one == 1 and s[i] == "0") or (one == 0 and s[i] == "1"):
            ng = 1
            break
    
    if ng == 1:
        print(-1)
    else:
        print("".join([str(i) for i in ANS]))


for _ in range(int(input())):
    s = input()
    n = len(s)
    x = int(input())
    
    w = ['1'] * len(s)
    
    for i in range(n):
        if s[i] == '0':
            if i + x < n:
                w[i + x] = '0'
            if i - x >= 0:
                w[i - x] = '0'
    
    temp = ['0'] * len(s)
    for i in range(n):
        if i + x < n:
            if w[i + x] == '1':
                temp[i] = '1'
        if i - x >= 0:
            if w[i - x] == '1':
                temp[i] = '1'
    if ''.join(temp) == s:
        print(''.join(w))
    else:
        print(-1)

t=int(input())
for you in range(t):
    s=input()
    n=len(s)
    x=int(input())
    arr=[1 for i in range(n)]
    poss=1
    for i in range(n):
        if(s[i]=='1'):
            if(i-x>=0 and arr[i-x]==0 and i+x<n and arr[i+x]==0):
                poss=0
                break
        else:
            if(i-x>=0):
                arr[i-x]=0
            if(i+x<n):
                arr[i+x]=0
    if(poss==0):
        print(-1)
        continue
    isposs=""
    for i in range(n):
        if(i-x>=0 and arr[i-x]):
            isposs=isposs+'1'
        elif(i+x<n and arr[i+x]):
            isposs=isposs+'1'
        else:
            isposs=isposs+'0'
    if(isposs==s):
        for i in arr:
            print(i,end="")
        print()
    else:
        print(-1)


import sys

sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

for _ in range(II()):
    s=SI()
    x=II()
    n=len(s)
    ans=[1]*n
    for i,c in enumerate(s):
        if c=="0":
            if i-x>=0:ans[i-x]=0
            if i+x<n:ans[i+x]=0

    def ok():
        for i in range(n):
            if s[i]=="1":
                flag=0
                if i-x>=0:flag|=ans[i-x]
                if i+x<n:flag|=ans[i+x]
                if flag==0:return False
        return True

    if ok():print(*ans,sep="")
    else:print(-1)