该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定整数$\red{k，}$现在有$\red{2^k}$支队伍（编号为$\red{1}$到$\red{2^k}$）进行共$\red{2^k-1}$场比赛，流程如下：

$\red{1. }$第$\red{1}$支与第$\red{2}$支进行比赛、第$\red{3}$支与第$\red{4}$支进行比赛，以此类推，这一阶段总共进行 队伍数除以 二场比赛。这些比赛中必定分出胜负，负方淘汰，胜方继续下一轮的比赛；

$\red{2. }$重复进行上述步骤，直到只有一支队伍没有被淘汰，这支队伍成为冠军。

（依据原题目描述中的图片来获得更好理解。该图满足$\red{k=3}$。）

给定一个长度为$\red{2^k-1}$的、仅包含字符 $\red{0 1 ? }$的字符串$\red{s，}$具体的：

如果$\red{s_i=}$"$\red{0}$"，表示第$\red{i}$次比赛中，编号更小的队伍获胜。

如果$\red{s_i=}$"$\red{1}$"，表示第$\red{i}$次比赛中，编号更大的队伍获胜。

如果$\red{s_i=}$"$\red?$"，表示第$\red{i}$次比赛中，任意一方都可能获胜。

设$\red{f(s)}$表示根据字符串$\red{s，}$所有可能成为冠军的不同的队伍数。

给定查询次数$\red{q，}$每次查询给定整数$\red{p}$和字符$\red{c，}$求将$\red{s}$的第$\red{p}$位修改为$\red{c}$后$\red{f(s)}$的值。

应注意的是，每次询问之间并不是互相独立的，也就是说每一次查询都会影响之后的查询。

输入格式

第一行一个整数$\red{k}$。 第二行包括一个长为$\red{2^k-1}$的字符串，表示初始时比赛情况。

第三行一个整数$\red{q，}$表示查询次数。

接下来$\red{q}$行，每行一个数字和一个字符 $\red{0 1 ? ，}$表示将第$\red{i}$场比赛结果修改为给定字符。

输出格式

对于每个询问，输出一行一个整数，表示$\red{f(s)}$。

样例

输入样例

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

输出样例

1
2
3
3
5
4

提示

对于$\red{50\%}$的数据，$\red{1<=q<=100,1<=k<=6}$。

对于$\red{100\%}$的数据，$\red{1<=k<=18,|s|=2^k-1,1<=q<=2\times 10^5}$。