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