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

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = "from bisect import bisect_left as bl\nfrom bisect import bisect_right as br\nfrom heapq import heappush,heappop,heapify\nimport math\nfrom collections import *\nfrom functools import reduce,cmp_to_key\nimport sys\ninput = sys.stdin.readline\n\nfrom itertools import accumulate\n\nM = mod = 998244353\ndef 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))))\ndef inv_mod(n):return pow(n, mod - 2, mod)\n \ndef li():return [int(i) for i in input().rstrip('\\n').split()]\ndef st():return input().rstrip('\\n')\ndef val():return int(input().rstrip('\\n'))\ndef li2():return [i for i in input().rstrip('\\n')]\ndef li3():return [int(i) for i in input().rstrip('\\n')]\n\n\n\nfor _ in range(val()):\n    l = [0] + li3()\n    x = val()\n    n = len(l) - 1\n    ans = [None] * (n + 1)\n    flag = 0\n\n    # print(l, n, x)\n    for i in range(1, n + 1):\n        # print(ans, i)\n        if l[i] == 1:\n            if i > x and (ans[i - x] == 1 or ans[i - x] == None):\n                ans[i - x] = 1\n            elif i + x <= n:\n                ans[i + x] = 1\n            else:\n                flag = 1\n                break\n        else:\n            if (i <= x or (ans[i - x] == None or ans[i - x ] == 0)) and (i + x > n or (ans[i + x] == None)):\n                if i > x:ans[i - x] = 0\n                if i + x <= n:ans[i + x] = 0\n            else:\n                flag = 1\n                break\n    for i in range(1, n + 1):\n        if ans[i] == None:ans[i] = 1  \n    if flag:\n        print(-1)\n    else:\n        print(*ans[1:n + 1], sep = '')"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 15507