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 = "import sys\n# sys.stdin = open('input.txt', 'r') \n# sys.stdout = open('output.txt', 'w')\n \nimport math\nimport collections\nfrom sys import stdin,stdout,setrecursionlimit\nimport bisect as bs\nsetrecursionlimit(2**20)\nM = 10**9+7\n    \nT = int(stdin.readline())\n# T = 1\n\nfor _ in range(T):\n    # n = int(stdin.readline())\n    # n,d,m = list(map(int,stdin.readline().split()))\n    # a = list(map(int,stdin.readline().split()))\n    # q = int(stdin.readline())\n    # a = list(map(int,stdin.readline().split()))\n    # b = list(map(int,stdin.readline().split()))\n    s = stdin.readline().strip('\\n')\n    x = int(stdin.readline())\n    n = len(s)\n    a = [-1]*n\n    res = True\n    for i in range(n):\n        if(s[i] == '1'):\n            if((i-x) >= 0 and a[i-x] != 0):\n                a[i-x] = 1\n                continue\n            if((i+x) < n):\n                if(a[i+x] == 0):\n                    res = False\n                    break\n                else:\n                    a[i+x] = 1\n                    continue\n            res = False\n            break\n        else:\n            if((i-x) >= 0):\n                if(a[i-x] == 1):\n                    res = False\n                    break\n                else:\n                    a[i-x] = 0\n            if((i+x) < n):\n                if(a[i+x] == 1):\n                    res = False\n                    break\n                else:\n                    a[i+x] = 0\n    ans = ''\n    for i in range(n):\n        if(a[i] != -1):\n            ans = ans + str(a[i])\n        else:\n            ans = ans + '1'\n    if(res): print(ans)\n    else: print(-1)\n"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13619