Рассмотрим следующий процесс. У вас есть бинарная строка (строка, состоящая только из символов 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\).
Выходные данные
На каждый набор входных данных выведите ответ:
- если не существует строки \(w\), которая может породить строку \(s\), то выведите \(-1\);
- иначе, выведите бинарную строку \(w\) состоящую из \(|s|\) символов. Если возможных ответов несколько — вы можете вывести любой из них.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
101110
2
01
1
110
1
|
111011
10
-1
|