Musha 最近在捣鼓一些电路，她的电路由信号（取值 0 或 1）以及与或门（仅支持两个输入端口）组成。其中的一些信号来自于 Musha 的设定，而另一些信号则由其他信号计算得到。

为了方便，Musha 使用两个小写英文字母（如 aa 或 bu ）描述信号，并用下列格式描述信号值的设定以及它们的连接方式：

aa := 0
bb := 1
cc <= aa & bb
dd <= cc | bb

上述四行中，aa 至 dd 均可以替换为其他信号名。

前两行表示，将信号 aa 的值设为 0，将 bb 的值设为 1；第三行表示将 aa 信号与 bb 信号使用与门连接，输出端口用 cc 表示，在此例中，cc 的值为 0；第四行表示将 cc 信号与 bb 信号使用或门连接，输出端口用 dd 表示。

请注意！与或门的输出结果信号，也可以再被连接到其他与或门的输入。各行之间的顺序不重要，因为它们描述的是设定或连接关系，而不是像 C 语言这样的“赋值”。

输入格式

在本题中，所有信号均使用两个小写字母表示。

第一行两个整数 n 与 q，使用空格隔开。n 表示设定与连接的总行数，q 表示询问的总数，你需要输出这 q 个信号的值。

接下来的 n 行，每行均为一句描述，将严格按照上述格式给出。数据保证，所有出现过的信号名，要么直接被设定为 0 或 1，要么是由另外两个信号计算得到。并且，每个信号只会在 := 或 <= 的左边出现一次。

数据同时保证不会出现循环依赖的情况，但不保证某个信号的第一次出现一定是位于 := 或 <= 的左边。

与或门的两个输入端口可能是同一个信号！如 aa <= bb & bb 是合法的。

接下来的 q 行，每行只有一个信号名，表示询问的信号名，你需要给出它的取值（0 或者 1）。

输出格式

q 行，每行一个 0 或 1，表示这 q 个信号的最终取值。

样例

Input

4 3
cc <= aa & bb
aa := 0
dd <= cc | bb
bb := 1
aa
cc
dd

Output

0
0
1

数据规模

$1 \leqslant n, q \leqslant 300$.