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

题目描述

小 C 热衷于学习数理逻辑。有一天，他发现了一种特别的逻辑表达式。在这种表达式中，所有操作数都是变量，取值只能为 $0$ 或 $1$，运算从左往右进行；如果表达式中有括号，则先计算括号内的子表达式。表达式只有以下三种运算：

1. 与运算：$a\ \&\ b$。当且仅当 $a$ 和 $b$ 的值都为 $1$ 时，结果为 $1$；其余情况结果为 $0$。
2. 或运算：$a\ |\ b$。当且仅当 $a$ 和 $b$ 的值都为 $0$ 时，结果为 $0$；其余情况结果为 $1$。
3. 取反运算：$!\ a$。当且仅当 $a$ 的值为 $0$ 时，结果为 $1$；其余情况结果为 $0$。

给定一个逻辑表达式和其中每个操作数的初始值。对于每次询问，将指定的一个操作数取反，并求此时原表达式的值。

表达式以后缀表达式的形式输入。操作数本身就是其后缀表达式；若 $E=E_1\ op\ E_2$，其后缀表达式为 $E_1'\ E_2'\ op$；若 $E=(E_1)$，其后缀表达式与 $E_1$ 相同。运算符两侧均有一个空格，表达式末尾没有空格。操作数由小写字母 x 和一个正整数下标拼接而成，例如 x10 表示变量 $x_{10}$。保证每个变量在表达式中恰好出现一次。

输入格式

从 expr.in 读入。

第一行包含一个字符串 $s$，表示后缀表达式。第二行包含一个正整数 $n$，表示变量个数；变量下标为 $1,2,\ldots,n$。第三行包含 $n$ 个空格分隔的整数，第 $i$ 个整数表示变量 $x_i$ 的初值，取值为 $0$ 或 $1$。第四行包含一个正整数 $q$，表示询问数。接下来 $q$ 行每行包含一个正整数，表示本次需要取反的变量下标。

每次询问的修改都是临时的，不影响之后的询问。保证表达式合法，变量初值为 $0$ 或 $1$。

输出格式

向 expr.out 输出 $q$ 行，每行包含一个 $0$ 或 $1$，表示对应询问下表达式的值。

样例

x1 x2 & x3 |
3
1 0 1
3
1
2
3

1
1
0

x1 ! x2 x4 | x3 x5 ! & & ! &
5
0 1 0 1 1
3
1
3
5

0
1
1

样例说明

样例 1 的中缀表达式是 $(x_1\ \&\ x_2)\ |\ x_3$。三次询问分别只取反一个变量，对应的初值依次变为 $(0,0,1)$、$(1,1,1)$、$(1,0,0)$，表达式的值分别为 1、1、0。

样例 2 的中缀表达式是 $(!x_1)\ \&\ (!((x_2\ |\ x_4)\ \&\ (x_3\ \&\ (!x_5))))$。

数据范围与提示

对于 $20\%$ 的数据，表达式中只有与运算符 & 或只有或运算符 |。

对于另外 $30\%$ 的数据，$|s|\le1000$，$q\le1000$，$n\le1000$。

对于另外 $20\%$ 的数据，变量初值全部为 $0$ 或全部为 $1$。

对于 $100\%$ 的数据，$1\le|s|\le10^6$，$1\le q\le10^5$，$2\le n\le10^5$。