[CSP-J 2020] 表达式

题目描述

小 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$。

给定一个逻辑表达式和其中每个变量的初值。之后有若干次询问，每次临时取反某一个变量的值，要求输出该次询问下原表达式的值。每次询问之间互不影响。

为便于处理，表达式采用后缀表达式输入。操作数由小写字母 x 与一个正整数拼接而成，例如 x10 表示变量 $x_{10}$。数据保证每个变量在表达式中恰好出现一次。

输入格式

第一行一个字符串 $s$，表示后缀逻辑表达式。

第二行一个正整数 $n$，表示变量数量。表达式中变量下标为 $1,2,\ldots,n$。

第三行 $n$ 个整数，第 $i$ 个整数表示变量 $x_i$ 的初值。

第四行一个正整数 $q$，表示询问数量。

接下来 $q$ 行，每行一个正整数，表示需要临时取反的变量下标。

输出格式

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

样例 #1

输入 #1

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

输出 #1

1
1
0

样例 #2

输入 #2

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

输出 #2

0
1
1

数据范围与提示

样例 #1 的中缀形式为 $(x_1 \operatorname{and} x_2) \operatorname{or} x_3$。

• 取反 $x_1$ 后，三个操作数依次为 $0,0,1$，表达式值为 $(0\&0)|1=1$。
• 取反 $x_2$ 后，三个操作数依次为 $1,1,1$，表达式值为 $(1\&1)|1=1$。
• 取反 $x_3$ 后，三个操作数依次为 $1,0,0$，表达式值为 $(1\&0)|0=0$。

样例 #2 的中缀形式为 $(\operatorname{not}x_1)\operatorname{and}(\operatorname{not}((x_2\operatorname{or}x_4)\operatorname{and}(x_3\operatorname{and}(\operatorname{not}x_5))))$。

数据范围与提示

• 对于 $20\%$ 的数据，表达式中只有与运算或只有或运算。
• 对于另外 $30\%$ 的数据，$|s| \le 1000$，$q \le 1000$，$n \le 1000$。
• 对于另外 $20\%$ 的数据，所有变量的初值全为 $0$ 或全为 $1$。
• 对于 $100\%$ 的数据，$1 \le |s| \le 10^6$，$1 \le q \le 10^5$，$2 \le n \le 10^5$。

其中 $|s|$ 表示字符串 $s$ 的长度。