$$$2^k$$$ 队参加季后赛。锦标赛由 $$$2^k - 1$$$ 场比赛组成。它们的举行方式如下:首先,球队被分成两对:球队$$$1$$$对阵球队$$$2$$$,球队$$$3$$$对阵球队$$$4$$$(完全按照这个顺序),依此类推(因此,$$$2^{k-1}$$$比赛在该阶段进行)。当一支球队输掉一场比赛时,该球队就会被淘汰,每场比赛都会导致一支球队被淘汰(没有平局)。之后,只剩下 $$$2^{k-1}$$$ 队。如果只剩下一支球队,则宣布该球队为冠军;否则,进行$$$2^{k-2}$$$游戏:在第一个游戏中,游戏的获胜者“$$$1$$$ vs $$$2$$$”与游戏的获胜者“$$$3$$$ vs $$$4$$$”,然后游戏的获胜者“$$$5$$$ vs $$$6$$$”与游戏的获胜者“$$$7$$$ vs $$$8$$$”,等等。重复此过程,直到只剩下一个团队。
例如,这张图描述了 $$$k = 3$$$ 的游戏的时间顺序:
设由 $$$2^k - 1$$$ 个字符组成的字符串 $$$s$$$ 按时间顺序描述游戏结果如下:
- 如果 $$$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)$$$ 作为查询结果。
输入
第一行包含一个整数 $$$k$$$ ($$$1 \le k \le 18$$$)。
第二行包含一个由 $$$2^k - 1$$$ 个字符组成的字符串 - 字符串 $$$s$$$ 的初始状态。每个字符都是 ?、0 或 1。
第三行包含一个整数 $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — 查询数。
接下来是 $$$q$$$ 行,第 $$$i$$$ 行包含一个整数 $$$p$$$ 和一个字符 $$$c$$$ ($$$1 \le p \le 2^k - 1$$$; $$$c$$$ 是 ?、0 或 1),描述第 $$$i$$$ 查询。
输出
对于每个查询,打印一个整数 — $$$f(s)$$$。
示例
输入 #1
3 0110?11 6 5 1 6 ? 7 ? 1 ? 5 ? 1 1
输出 #1
1 2 3 3 5 4