题目描述

现给出一个后缀形式的逻辑表达式，其中只包含三种逻辑运算符：与(&)、或(|)、非(!)。

其中，操作数为变量，用 $x_i$ 来表示（ $i$ 为正整数），具体为 $x1、x2、x3~...~x_n$ ，操作数、操作符之间都由一个空格隔开。

数据保证每个变量仅在表达式中出现一次。

接下来给出 $m$ 次询问，每次询问会临时将一个变量的值取反，请计算出取反后表达式的值是多少。

注意：本次取反修改的值不保留，即不会影响下一次询问

输入格式

第一行为字符串 $s$，即后缀形式的逻辑表达式。 第二行为正整数 $n$，即表达式中变量的数量。 第三行为 $n$ 个整数，即变量 $x_i$ 的值，仅包含 $0$ 或者 $1$。 第四行为正整数 $m$，即询问的次数。 接下来 $m$ 行，每行一个正整数，表示需要取反的变量的下标（从 $1$ 开始）。

输出格式

输出一共有 $m$ 行，每行为 $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~\&~x_2)~|~x_3$。 其中 $x_1,x_2,x_3$ 的值分别为 $1,0,1$。

三次询问如下：

• $x_1$ 取反。 $(0~\&~0)~|~1=1$。
• $x_2$ 取反。 $(1~\&~1)~|~1=1$。
• $x_3$ 取反。 $(1~\&~0)~|~0=0$。

样例 2 解释

该样例的中缀表达式为：$!x_1~\&~!((x_2~|~x_4)~\&~(x_3~\&~!x_5))$。

数据规模与约定

字符串 $s$ 的长度记作$|s|$，有：

$1 \le |s| \le 1 \times 10^6$， $1 \le m \le 1 \times 10^5$， $2 \le n \le 1 \times 10^5$。