$$$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)$$$ в результате запроса.