\(2^k\) команд участвуют в плей-офф турнире. Турнир состоит из \(2^k - 1\) игры. Они проводятся следующим образом: во-первых, команды делятся на пары: команда \(1\) играет против команды \(2\), команда \(3\) играет против команды \(4\) (именно в таком порядке) и так далее (таким образом, в этой фазе будет сыграно \(2^{k-1}\) игры). Когда команда проигрывает игру, она выбывает, и каждая игра приводит к выбыванию одной команды (нет ничьих). После этого остается \(2^{k-1}\) команд. Если остается только одна команда, она объявляется чемпионом; в противном случае играется еще \(2^{k-2}\) игр: в первой из них победитель игры «\(1\) против \(2\)» играет против победителя игры «\(3\) против \(4\)», затем победитель игры «\(5\) против \(6\)» играет против победителя игры «\(7\) против \(8\)» и так далее. Этот процесс повторяется до тех пор, пока не останется только одна команда.
Например, на этом рисунке описан хронологический порядок игр с \(k = 3\):
Пусть строка \(s\), состоящая из \(2^k - 1\) символов, описывает результаты игр в хронологическом порядке следующим образом:
- если \(s_i\) равно 0, то команда с меньшим индексом выигрывает \(i\)-ю игру;
- если \(s_i\) равно 1, то команда с большим индексом выигрывает \(i\)-ю игру;
- если \(s_i\) равно ?, то результат \(i\)-й игры неизвестен (любая команда может выиграть эту игру).
Пусть \(f(s)\) — число возможных победителей турнира, описываемого строкой \(s\). Команда \(i\) является возможным победителем турнира, если можно заменить каждый ? на 1 или 0 таким образом, что команда \(i\) является чемпионом.
Вам дается начальное состояние строки \(s\). Вы должны обработать \(q\) запросов следующей формы:
- \(p\) \(c\) — заменить \(s_p\) символом \(c\) и вывести \(f(s)\) в результате запроса.