Аня украшает свой офис самыми крутыми лампами. Она использует очень длинные светодиодные ленты, в которых каждая отдельная ячейка включается или выключается каждую секунду по следующему простому и красивому алгоритму. На каждом шаге статус каждой ячейки (0 для выкл. и 1 для вкл.) определяется из состояния двух соседних ячеек на полосе (левой и правой) и собственного состояния, согласно к следующей таблице:
Аня выбирает первоначальную конфигурацию ячеек и восхищается получившейся анимацией, которая очень похожа на "Игру жизни" Конвея, с интересным поведением на границе между стабильностью и хаосом.
Первая строка содержит исходную конфигурацию в виде строки из 16 символов 0 и 1. Все ячейки слева и справа от этой строки считаются 0.
Вторая строка содержит количество n (0≤n<260) шагов, которые необходимо выполнить.
Светодиодная лента считается достаточно большой, чтобы ни одна 1-ячейка никогда не достигла концов ленты.
Выведите одно целое число, которое представляет собой общее количество 1-ячеек в окончательной конфигурации.
Ответ равен 11, выполнены будут следующие пять шагов:
где все, что не отображается, содержит только 0-ячейки.