许多编程语言允许你定义自定义比较器来对用户定义的对象进行排序。 IFFY 是一种编程语言，其唯一的程序就是旨在作为比较器的函数。这些函数对位串（以下称为“字”）进行操作。字从左侧第一个字符开始，以 1 为索引。

要在 IFFY 中编写一个关于两个字的函数，程序员需要编写一系列 if 语句。每个 if 语句从第一个字中选择一个位，从第二个字中选择一个位，并对这两个位求某个表达式的值。如果表达式在所选位上求值为 1，则函数立即返回指定的返回值。否则，执行流程将进入下一条 if 语句，不返回任何值。

每条 if 语句的语法为 a b expr r，其中整数 a 指定第一个字中的一个位，整数 b 指定第二个字中的一个位，expr 是使用变量 x 和/或 y 的布尔表达式，r 是当表达式求值为 1 时函数返回的值（0 或 1）。变量 x 指代第一个字中的指定位，变量 y 指代第二个字中的指定位。例如，考虑 if 语句 2 3 x|y 0。该表达式的含义是：如果第一个字的第 2 位或第二个字的第 3 位被置位，则返回 0，否则继续执行下一条语句。

有效表达式的语法如下： x、y、0 和 1 是有效表达式。 如果 E 是有效表达式，则 (E) 是有效表达式。 如果 E 是有效表达式，则 !E 是有效表达式。 如果 E1 和 E2 是有效表达式，则所有形式为 E1⊕E2 的字符串都是有效表达式，其中 ⊕ 是 =（相等）、&（与）、|（或）或 ^（异或）之一。

括号的优先级最高，其次是单目运算符 !，然后依次是二元运算符 =、&、| 和 ^。所有二元运算符都是左结合的。表达式中没有空格。

各运算符的真值表如下：

图 1：唯一单目运算符的真值表。

图 2：二元运算符的真值表。

为了使函数 $f(x, y)$ 能正常作为比较器运行，它必须满足某些属性。非正式地讲，为了使 $f(x, y)$ 成为比较器，它应该施加某种顺序 $<$，其中 $f(x, y)$ 当且仅当 $x < y$ 时返回 1。更正式地讲，比较器必须满足的三个属性是自反性、对称性和传递性，如下所示：

1. 自反性：对于所有 $x$，$f(x, x)$ 应返回 0。
2. 对称性：对于所有 $x, y$，如果 $f(x, y)$ 返回 1，则 $f(y, x)$ 必须返回 0。
3. 传递性：对于所有 $x, y, z$，如果 $f(x, y)$ 和 $f(y, z)$ 都返回 1，则 $f(x, z)$ 也必须返回 1。

给定一个 IFFY 语言编写的函数，通过计算它们被违反的频率来确定它满足这三个属性的程度。首先，在给定长度的所有字中，计算自反性失效的字的个数。其次，计算对称性失效的字对的个数。最后，计算传递性失效的字三元组的个数。

输入格式

第一行包含两个整数 $n$ ($0 \le n \le 2 \cdot 10^5$) 和 $k$ ($1 \le k \le 10$)，其中 $n$ 是函数中的行数，$k$ 是被比较值的位数。 接下来的 $n$ 行，每行包含四个标记，形式为 a b expr r，其中 $a$ 和 $b$ ($1 \le a, b \le k$) 是 $x$ 和 $y$ 中要考虑的位的索引，expr 是一个有效表达式，$r$ ($0 \le r \le 1$) 是返回值。 最后一行给出了如果没有触发任何 if 语句时的返回值。所有表达式的总长度最多为 $10^6$。

输出格式

输出一行，包含三个空格分隔的整数。第一个整数是自反性被违反的字的个数，第二个整数是对称性被违反的字对的个数，第三个整数是传递性被违反的字三元组的个数。

样例

样例 1

3 2
1 1 (x=0)&(y=1) 1
1 1 (x=1)&(y=(x^x)) 0
2 2 (x=1)|(y=0) 0
1

0 0 0

样例 2

4 3
2 1 x=0&(y=1) 1
1 2 !x^!!y 0
2 3 ((x|1)=y)&1&1 1
3 1 !x&!x&!x 0
1

3 25 52