#CSPJ2020C. 表达式 (Expression)

表达式 (Expression)

Description

Little C is eager to learn mathematical logic. One day, he discovered a special logical expression. In this kind of logical expression, all operands are variables and can only take the values 00 and 11. The calculation proceeds from left to right. If there are parentheses in the expression, the value of the sub-expression inside the parentheses is calculated first. In particular, this expression has only the following operations:

  1. AND operation: a & b. If and only if the values of both aa and bb are 11, the value of the expression is 11. Otherwise, the value of the expression is 00.
  2. OR operation: a | b. If and only if the values of both aa and bb are 00, the value of the expression is 00. Otherwise, the value of the expression is 11.
  3. Negation operation: !a. If and only if the value of aa is 00, the value of the expression is 11. Otherwise, the value of the expression is 00.

Given a logical expression and the initial value of each operand, Little C wants to know the value of the original expression when the value of an operand is inverted.

In order to simplify the processing of expressions, we have the following conventions:

The expression will be given in the form of a postfix expression.

A postfix expression is defined as follows:

  1. If EE is an operand, the postfix expression of EE is EE itself.
  2. If EE is an expression of the form E1 op E2E_1~\texttt{op}~E_2, where op\texttt{op} is any binary operator with precedence no higher than the precedences of the operators outside the parentheses in E1E_1 and E2E_2, then the postfix expression of EE is E1 E2 opE_1'~E_2'~\texttt{op}, where E1E_1' and E2E_2' are the postfix expressions of E1E_1 and E2E_2 respectively.
  3. If EE is an expression of the form E1E_1, the postfix expression of EE is the postfix expression of E1E_1.

For convenience while taking input, there is a space around the AND operator (&), the OR operator (|), and the negation operator (!), but there is no space at the end of the input expression.

An operand is formed by concatenating the lowercase letter x with a positive integer which represents the subscript of this variable. For example, x10 represents the variable x10x_{10}. It is guaranteed that each variable appears exactly once in the expression.

Input Format

The first line contains a string ss denoting the expression as described above.

The second line contains a positive integer nn denoting the number of variables in the expression. The subscripts of the variables in the expression are 1,2,,n1, 2, \cdots, n.

The third line contains nn integers, where the ii-th integer denotes the initial value of the variable xix_i.

The fourth line contains a positive integer qq denoting the number of queries.

Each of the next qq lines contains a positive integer denoting the subscript of the variable that needs to be inverted. Note that the modification done in each query is temporary, i.e., the modification done in the previous query doesn't affect the subsequent query.

It is guaranteed that the given expression is valid and the initial value of each variable is 00 or 11.

Output Format

Print qq lines, one per query, containing the value of the expression (00 or 11) for that query.

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

The infix expression equivalent to the given postfix expression is (x1&x2)x3(x_1 \& x_2) | x_3.

In the first query, the value of x1x_1 is inverted. Now the values of the three variables are 0,0,10, 0, 1. The value of the original expression is (0&0)1=1(0 \& 0) | 1 = 1.

In the second query, the value of x2x_2 is inverted. Now the values of the three variables are 1,1,11, 1, 1. The value of the original expression is (1&1)1=1(1 \& 1) | 1 = 1.

In the third query, the value of x3x_3 is inverted. Now the values of the three variables are 1,0,01, 0, 0. The value of the original expression is (1&0)0=0(1 \& 0) | 0 = 0.

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

The infix expression equivalent to the given postfix expression is (!x1)&(!((x2x4)&(x3&(!x5))))(!x_1) \& (!((x_2 | x_4) \& (x_3 \& (!x_5)))).

Constraints

For 20%20\% of the data, the expression contains only the AND operation (&) or only the OR operation (|).
For another 30%30\% of the data, s1000,q1000,n1000|s| \le 1000, q \le 1000, n \le 1000.
For another 20%20\% of the data, the initial values of the variables are all 00 or all 11.
For 100%100\% of the data, 1s106,1q105,2n1051 \le |s| \le 10^6, 1 \le q \le 10^5, 2 \le n \le 10^5.

s|s| represents the length of the string ss.