Problem 8E. 逻辑表达式

时间限制：1000ms​

空间限制：256MB​

题目描述

这个学期\(lhy\)正在学习数字逻辑电路，逻辑代数是一个重点。\(lhy\)作为一名计电院的学生，十分喜欢使用计算器，但是很可惜，一般的计算器都不支持逻辑运算。于是\(lhy\)找到了你，想和你合作写一个可以实现逻辑运算的计算器，减少学习的痛苦。\(lhy\)已经完成了大部分工作，现在还缺少一个计算逻辑表达式的算法，你将这部分完成就可以了。

按照\(lhy\)的接口设计，算法的输入包含一个逻辑表达式和一组赋值，算法的输出是一个确定的逻辑常量。

逻辑常量，只有\(0\)和\(1\)两种，表示对立的状态。

逻辑变量，一些由字母表示的量，类似于代数中的变量\(x,y,z\)等，但是这里的逻辑变量只能取\(0\)和\(1\)两种。

赋值，给逻辑变量取定一个值称为赋值，比如下表(逻辑运算符中)就是\(4\)组不同的赋值。

逻辑运算符，只需要包含如下三种即可：与(&),或(|),非(!)，优先级为非最高，与或同级。

逻辑表达式，包含逻辑常量，逻辑变量，逻辑运算符以及括号。与一般的代数式相同，括号可以改变式子的运算顺序。

注意，\(lhy\)会保证输入的逻辑表达式一定是合法的，所有的赋值是唯一的，不会出现没有赋值的逻辑变量。

此外，由于在python中，and的优先级是在or之上的，而本题要求二者同级，所以你并不能直接使用内置的\(eval\)函数。

数据格式

输入

第一行，一个正整数\(T\)，表示测试用例的数量。

每个测试用例的输入如下：

第一行，一个合法的逻辑表达式\(expression\)。

第二行，一个非负整数\(n\)，表示逻辑表达式含有的逻辑变量个数。

接下来\(n\)行，每行一个字符\(key\)和一个逻辑常量\(value\)，表示名为\(key\)的逻辑变量取值为\(value\).

输出

一个逻辑常量。

样例1

输入

4
1|0&0
2
a 1
B 0
!(t|r|a|t|S)&!(t|c|a|p|m|I|n|i|h|s|n|e|G)
14
G 0
e 0
s 0
h 0
i 0
n 0
I 0
m 0
p 0
c 0
S 0
a 0
r 0
t 0
(H&o|n|k&|a&!i|S|!t|a|r&R&a&i|l)
11 
H 0
o 1
n 0
k 0
S 0
t 0
r 0
R 1
a 1
i 1
l 0
n&n&u
52
a 1
b 0
c 0
d 0
e 1
f 1
g 0
h 1
i 0
j 1
k 1
l 1
m 0
n 0
o 1
p 1
q 0
r 0
s 1
t 1
u 1
v 1
w 1
x 0
y 1
z 0
A 1
B 1
C 1
D 1
E 1
F 0
G 1
H 1
I 0
J 0
K 1
L 0
M 0
N 1
O 0
P 1
Q 1
R 1
S 1
T 0
U 0
V 0
W 0
X 0
Y 0
Z 1

输出

0
1
1
0

数据范围及约定

数据保证\(key\)的命名只取小写字母\(a\)~\(z\)以及大写字母\(A\)~\(Z\)，共计\(52\)种.

数据保证表达式的长度之和\(\sum|expression|\)不超过\(10^6\).

数据中的逻辑变量不一定按照出现的顺序赋值，也可能会有冗余的赋值。