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 = 't = int(input())\nfor i in range(t):\n    s = input()\n    m = len(s)\n    x = int(input())\n    ANS = [1] * m\n    for i in range(m):\n        if s[i] == "0":\n            if i-x >= 0:\n                ANS[i-x] = 0\n            if i+x < m:\n                ANS[i+x] = 0\n    \n    ng = 0\n    for i in range(m):\n        one = 0\n        if (i-x >= 0 and ANS[i-x] == 1) or (i+x < m and ANS[i+x] == 1):\n            one = 1\n        if (one == 1 and s[i] == "0") or (one == 0 and s[i] == "1"):\n            ng = 1\n            break\n    \n    if ng == 1:\n        print(-1)\n    else:\n        print("".join([str(i) for i in ANS]))\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13345