C. Восстановление бинарной строки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рассмотрим следующий процесс. У вас есть бинарная строка (строка, состоящая только из символов 0 и 1) $$$w$$$ длины $$$n$$$ и число $$$x$$$. Вы создаете новую бинарную строку $$$s$$$ длины $$$n$$$; $$$i$$$-й символ новой строки $$$s$$$ выбирается следующим образом:

  • если символ $$$w_{i-x}$$$ существует и равен 1, то $$$s_i$$$ равно 1 (более формально, если $$$i > x$$$ и $$$w_{i-x} = $$$ 1, то $$$s_i = $$$ 1);
  • если символ $$$w_{i+x}$$$ существует и равен 1, то $$$s_i$$$ равно 1 (более формально, если $$$i + x \le n$$$ и $$$w_{i+x} = $$$ 1, то $$$s_i = $$$ 1);
  • если оба описанных выше условия неверны, то $$$s_i$$$ равно 0.

Вам заданы число $$$x$$$ и строка $$$s$$$. Восстановите изначальную строку $$$w$$$.

Входные данные

Первая строка содержит число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных.

Каждый набор входных данных содержит две строки. Первая строка содержит строку $$$s$$$ ($$$2 \le |s| \le 10^5$$$, каждый символ строки $$$s$$$ равен либо 0, либо 1). Вторая строка содержит целое число $$$x$$$ ($$$1 \le x \le |s| - 1$$$).

Суммарная длина всех длин строк $$$s$$$ во входных данных не превосходит $$$10^5$$$.

Выходные данные

На каждый набор входных данных выведите ответ:

  • если не существует строки $$$w$$$, которая может породить строку $$$s$$$, то выведите $$$-1$$$;
  • иначе, выведите бинарную строку $$$w$$$ состоящую из $$$|s|$$$ символов. Если возможных ответов несколько — вы можете вывести любой из них.
Пример
Входные данные
3
101110
2
01
1
110
1
Выходные данные
111011
10
-1