题目描述

George 在学位运算。他编了一个位运算表达式，但是他不会高效计算这个表达式的值，于是他找 Dream 帮他计算。
George 的表达式有 $64$ 个 01 变量，分别编号为 $0$ 到 $63$。他提供了该表达式的后缀表示法。
后缀表示法里可能含有以下符号：

• $0,1,\dots,63$，代表对应变量
• !&|^，代表对应位运算

现在 Dream 有 $m$ 个情况。每一个情况固定所有 $64$ 个变量的值。他需要你对每一个情况计算给定表达式的值。
为了方便输入，这些情况进行压缩。定义 $a_{i,j}$ 为第 $i$ 情况里的第 $j$ 变量值，其中 $a_{i,j}\in\{0,1\}$；他会给你

可以证明，如果 $0\le b_i<2^{64}$，则 $b_i$ 唯一对应一组 $a_{i,0},a_{i,1},\dots,a_{i,63}$。

输入格式

第一行一个正整数 $n$，表示后缀表示法的长度。
接下来一行 $n$ 个符号，表示 George 的表达式。
接下来一行一个正整数 $m$。
接下来一行 $m$ 个整数，依次代表 $b_1,b_2,\dots,b_m$。

输出格式

输出 $m$ 个 01 字符，其中第 $i$ 输出字符代表第 $i$ 情况时，表达式的值。

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

提示

样例 1 解释

如果 $x=1$，则变量 $0$ 为 $1$，其余变量为 $0$。
如果 $x=9$，则仅变量 $0$ 和 $3$ 为 $1$。

数据规模与约定

本题采用捆绑测试。

• 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）：没有额外限制。

对于所有数据，$1\le n,m\le10^5$，$0\le b_i<2^{64}$。