Efficient Bitwise Expression Evaluation

George is studying bitwise operations for his degree. He wrote a complex bitwise expression but is not able to compute its value efficiently. He has prepared the expression in postfix notation and seeks Dream's help to evaluate it quickly.

The expression consists of 64 binary variables, denoted by a₀, a₁, ..., a₆₃, where each variable is either 0 or 1. In the expression, a variable is represented by its index (an integer between 0 and 63). The operators in the expression include:

• !: Logical (bitwise) NOT. It is a unary operator which converts 0 to 1 and 1 to 0.
• &: Bitwise AND.
• |: Bitwise OR.
• ^: Bitwise XOR.

The expression is given in postfix notation (also known as reverse Polish notation). For example, the postfix expression

0\ 1\ &\ 2\ |\ !

corresponds to the infix expression:

$$!\Bigl((a_{0}\ \&\ a_{1})\ |\ a_{2}\Bigr)$$

Dream has m different scenarios. In each scenario, the values of all 64 variables are fixed. Instead of providing all 64 bits explicitly, each scenario is compressed into a single unsigned 64-bit integer b_i defined as follows:

$$b_i = \sum_{j=0}^{63} a_{i,j}2^j,$$

where \(a_{i,j}\) is the value of the j-th variable in the i-th scenario. It can be proven that if \(0\le b_i <2^{64}\), then \(b_i\) uniquely determines the 64 variable values.

Your task is to compute the value of the given postfix expression for each scenario.

inputFormat

The input begins with a line containing the postfix expression. The tokens in the expression are separated by single spaces. Each token is either an integer (in the range 0 to 63) representing a variable, or one of the operators: !, &, |, or ^.

The next line contains a single integer m (number of test cases).

Following that, there are m lines, each containing an unsigned 64-bit integer b_i which encodes the values of the 64 variables for that test case. You can obtain the value of the variable corresponding to index j by checking the \(j\)-th bit of b_i (with the least significant bit corresponding to index 0).

outputFormat

For each test case, output a single line containing the computed value of the postfix expression (which will be either 0 or 1).

sample

0 1 & 2 | !
4
0
2
3
7

1
1
0
0

</p>