淘汰赛

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

有 $2^k$ 支队伍参加一场淘汰赛。第一轮中，第 $1$ 支队伍与第 $2$ 支队伍比赛，第 $3$ 支队伍与第 $4$ 支队伍比赛，依此类推。每场比赛都会淘汰一支队伍。此后，每一轮都让上一轮相邻两场比赛的胜者继续比赛，直到产生唯一的冠军。

下图展示了 $k=3$ 时各场比赛的顺序。

全部 $2^k-1$ 场比赛按照实际进行的先后顺序编号，并由一个长度为 $2^k-1$ 的字符串 $s$ 描述：

• 若 $s_i=0$，第 $i$ 场比赛中编号较小的队伍获胜；
• 若 $s_i=1$，第 $i$ 场比赛中编号较大的队伍获胜；
• 若 $s_i=?$，第 $i$ 场比赛的结果尚未确定，两支队伍都可能获胜。

令 $f(s)$ 表示可能成为冠军的队伍数量。若存在一种把所有问号替换为 $0$ 或 $1$ 的方式，使某支队伍成为冠军，则这支队伍被计入 $f(s)$。

给定初始字符串 $s$，你需要依次处理 $q$ 次修改。每次修改把 $s_p$ 改成字符 $c$，并求出修改后的 $f(s)$。

输入格式

第一行包含一个整数 $k$（$1\le k\le18$）。

第二行包含一个长度为 $2^k-1$ 的字符串 $s$，其中每个字符都是 0、1 或 ?。

第三行包含一个整数 $q$（$1\le q\le2\times10^5$）。

接下来 $q$ 行，每行包含一个整数 $p$ 和一个字符 $c$（$1\le p\le2^k-1$，$c$ 为 0、1 或 ?），表示把 $s_p$ 修改为 $c$。

输出格式

对于每次修改，输出一行一个整数，表示修改后的 $f(s)$。

样例输入 1

3
0110?11
6
5 1
6 ?
7 ?
1 ?
5 ?
1 1

样例输出 1

1
2
3
3
5
4

数据范围

对于所有测试数据，$1\le k\le18$，$|s|=2^k-1$，$1\le q\le2\times10^5$，$1\le p\le2^k-1$。