Problem Description

Xiao C is keen on studying mathematical logic. One day, he discovered a special kind of logical expression. In this kind of logical expression, all operands are variables, and their values can only be $0$ or $1$. The operations are evaluated from left to right. If there are parentheses in the expression, the value of the subexpression inside the parentheses is calculated first. In particular, this kind of expression has and only has the following operations:

1. AND operation: a & b. If and only if both $a$ and $b$ are $1$, the value of this expression is $1$. In all other cases, the value is $0$.
2. OR operation: a | b. If and only if both $a$ and $b$ are $0$, the value of this expression is $0$. In all other cases, the value is $1$.
3. NOT operation: !a. If and only if $a$ is $0$, the value of this expression is $1$. In all other cases, the value is $0$.

Xiao C wants to know: given a logical expression and the initial value of each operand in it, after negating the value of one operand, what is the value of the original expression?

To simplify processing the expression, we make the following conventions:

The expression will be given in postfix notation.

The definition of postfix notation is as follows:

1. If $E$ is an operand, then the postfix form of $E$ is itself.
2. If $E$ is an expression of the form $E_1~\texttt{op}~E_2$, where $\texttt{op}$ is any binary operator, and its precedence is not higher than the operators outside parentheses in $E_1$ and $E_2$, then the postfix form of $E$ is $E_1' E_2' \texttt{op}$, where $E_1'$ and $E_2'$ are the postfix forms of $E_1$ and $E_2$, respectively.
3. If $E$ is an expression of the form $E_1$, then the postfix form of $E_1$ is the postfix form of $E$.

Also, for convenience, in the input:

1. There is exactly one space on both sides of the AND operator (&), OR operator (|), and NOT operator (!), but there is no trailing space at the end of the expression.
2. Each operand is formed by concatenating a lowercase letter x and a positive integer. The positive integer is the index of the variable. For example, x10 means the variable $x_{10}$ with index $10$. The testdata guarantees that each variable appears exactly once in the expression.

Input Format

The first line contains a string $s$, representing the expression described above.

The second line contains a positive integer $n$, representing the number of variables in the expression. The indices of variables in the expression are $1,2,\cdots,n$.

The third line contains $n$ integers. The $i$-th integer represents the initial value of variable $x_i$.

The fourth line contains a positive integer $q$, representing the number of queries.

The next $q$ lines each contain one positive integer, representing the index of the variable to be negated. Note that each modification in a query is temporary, i.e., modifications in previous queries do not affect subsequent queries.

The testdata guarantees that the input expression is valid. The initial values of variables are $0$ or $1$.

Output Format

Output $q$ lines. Each line contains a $0$ or $1$, representing the value of the expression under that query.

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

Hint

Explanation for Sample 1

The infix form of this postfix expression is $(x_1 \operatorname{and} x_2) \operatorname{or} x_3$.

• For the first query, negate the value of $x_1$. Then the values of the three operands are $0$, $0$, $1$ in order. The value of the original expression is $(0\&0)|1=1$.
• For the second query, negate the value of $x_2$. Then the values of the three operands are $1$, $1$, $1$ in order. The value of the original expression is $(1\&1)|1=1$.
• For the third query, negate the value of $x_3$. Then the values of the three operands are $1$, $0$, $0$ in order. The value of the original expression is $(1\&0)|0=0$.

Explanation for Sample 2

The infix form of this expression is $(\operatorname{not}x_1)\operatorname{and}(\operatorname{not}((x_2\operatorname{or}x_4)\operatorname{and}(x_3\operatorname{and}(\operatorname{not}x_5))))$.

Constraints

• For $20\%$ of the testdata, the expression contains only AND operations (&) or only OR operations (|).
• For another $30\%$ of the testdata, $|s| \le 1000$, $q \le 1000$, and $n \le 1000$.
• For another $20\%$ of the testdata, the initial values of all variables are all $0$ or all $1$.
• For $100\%$ of the testdata, $1 \le |s| \le 1 \times 10^6$, $1 \le q \le 1 \times 10^5$, and $2 \le n \le 1 \times 10^5$.

Here, $|s|$ denotes the length of the string $s$.

Translated by ChatGPT 5