Description

George is studying bitwise operations. He wrote a bitwise expression, but he cannot compute its value efficiently, so he asked Dream to help him compute it.

George's expression has $64$ binary variables, numbered from $0$ to $63$. He provides the postfix notation of the expression.

The postfix notation may contain the following symbols:

• $0,1,\dots,63$, representing the corresponding variables.
• !&|^, representing the corresponding bitwise operations.

Now Dream has $m$ cases. In each case, the values of all $64$ variables are fixed. You need to compute the value of the given expression for each case.

To make input easier, these cases are compressed. Let $a_{i,j}$ be the value of variable $j$ in case $i$, where $a_{i,j}\in\{0,1\}$. You are given

It can be proven that if $0\le b_i<2^{64}$, then $b_i$ uniquely corresponds to a set of $a_{i,0},a_{i,1},\dots,a_{i,63}$.

Input Format

The first line contains a positive integer $n$, indicating the length of the postfix notation.

The next line contains $n$ symbols, representing George's expression.

The next line contains a positive integer $m$.

The next line contains $m$ integers, representing $b_1,b_2,\dots,b_m$ in order.

Output Format

Output $m$ characters, each being 0 or 1. The $i$-th output character represents the value of the expression in the $i$-th case.

8
0 1 ^ 2 3 ! & |
7
1 9 1 9 8 1 0

1111010

23
0 ! ! 3 0 3 ^ ^ 3 | & 1 ! ^ 2 0 ! 3 ^ ! ^ ! ^
20
11 10 4 8 13 7 2 5 11 9 16 15 6 9 7 8 15 0 2 10

00110011010101011010

Hint

Explanation for Sample 1

If $x=1$, then variable $0$ is $1$, and all other variables are $0$.

If $x=9$, then only variables $0$ and $3$ are $1$.

Constraints

This problem uses bundled testdata.

• Subtask 1 (7 pts): $n,m\le10^3$.
• Subtask 2 (11 pts): $b_i\in[0,2^{8}-1]$.
• Subtask 3 (41 pts): $n,m\le5\times10^4$.
• Subtask 4 (41 pts): no additional constraints.

For all testdata, $1\le n,m\le10^5$, $0\le b_i<2^{64}$.

Translated by ChatGPT 5