在本题中，你需要根据给定的表达式对集合进行运算。

考虑一个涉及三个集合 $A$、$B$ 和 $C$ 以及三种集合运算（并集、交集和补集）的表达式。

对于本题，集合仅包含 $\{1, 2, \dots, n\}$ 中的数字，其中 $n$ 为某个固定的整数。集合 $X$ 和 $Y$ 的并集是一个包含所有出现在 $X$ 或 $Y$ 中至少一个集合里的数字的集合。集合 $X$ 和 $Y$ 的交集是一个包含所有同时出现在 $X$ 和 $Y$ 中的数字的集合。集合 $X$ 的补集是一个包含范围 $\{1, 2, \dots, n\}$ 中所有不在 $X$ 中的数字的集合。例如，若 $n = 5$，$X = \{3, 4\}$ 且 $Y = \{1, 3\}$，则 $X$ 和 $Y$ 的并集为 $\{1, 3, 4\}$，它们的交集为 $\{3\}$，而 $X$ 的补集为 $\{1, 2, 5\}$。

表达式的递归定义如下： $A$、$B$ 和 $C$ 是分别表示三个给定集合 $A$、$B$ 和 $C$ 的表达式。 如果 $E$ 是一个表达式，则 $\sim E$ 和 $(E)$ 也是表达式。 * 如果 $E$ 和 $F$ 是表达式，则 $E|F$ 和 $E\&F$ 也是表达式。

其中，$\sim X$ 是集合 $X$ 的补集，$X|Y$ 是集合 $X$ 和 $Y$ 的并集，$X\&Y$ 是集合 $X$ 和 $Y$ 的交集。补运算的优先级高于交运算，交运算的优先级高于并运算。括号在确定运算优先级时起常规作用。例如，表达式 $A|\sim B\&C$ 的计算方式与 $A|((\sim B)\&C)$ 相同。

给定一个表达式和多组集合 $A$、$B$ 和 $C$ 的三元组，请计算并输出每组三元组对应的表达式结果。

输入格式

输入的第一行包含该表达式。其长度在 $1$ 到 $300\,000$ 个字符之间。保证表达式符合上述递归定义。第一行不包含空格。

第二行包含两个整数 $n$ 和 $t$，用空格分隔：表示集合中元素的范围上限和三元组的数量（$1 \le n \le 20$，$1 \le t \le 10\,000$）。

接下来的 $t$ 行，每行描述一个集合三元组 $A$、$B$ 和 $C$。集合由该集合中包含的整数列表表示，数字按严格升序排列，并以 $0$ 结尾。数字之间由一个或多个空格分隔。

输出格式

对于给定的 $t$ 组三元组中的每一组，输出一行，包含一个集合：即给定 $A$、$B$ 和 $C$ 时表达式的计算结果。集合必须写成包含在其中的整数列表，按严格升序排列，并以 $0$ 结尾。数字之间用一个或多个空格分隔。

样例

输入 1

A|~B&C
5 2
1 3 0 3 4 0 2 3 5 0
0 1 3 5 0 0

输出 1

1 2 3 5 0
0

说明

在此示例中，表达式按 $A|((\sim B)\&C)$ 进行计算。对于第一组三元组，$\sim B = \{1, 2, 5\}$，$\sim B\&C = \{2, 5\}$，整个表达式的结果为 $\{1, 2, 3, 5\}$。对于第二组三元组，$\sim B = \{2, 4\}$，$\sim B\&C$ 为空集，结果也为空集。