Comparator

Many programming languages let you define custom comparators to sort user-defined objects.

IFFY is a programming language where the only programs are functions intended to be comparators. These functions operate on bitstrings, called "words". Words are 1-indexed starting with the leftmost character.

To write a function on two words in IFFY, the programmer writes a series of if-statements. Each if statement chooses a bit from the first word, a bit from the second word, and evaluates an expression on those two bits. If the expression evaluates to $1$ on those chosen bits, the function returns immediately with a specified return value. Otherwise, execution falls through to the next if statement.

The syntax of each if statement is a b expr r. The integer $a$ specifies a bit from the first word, the integer $b$ specifies a bit from the second word, expr is a boolean expression using the variables x and/or y, and $r$ is the value ($0$ or $1$) returned if the expression evaluates to $1$. The variable x refers to the chosen bit in the first word, and y refers to the chosen bit in the second word. For example, the if statement 2 3 x|y 0 means: if the second bit of the first word or the third bit of the second word is set, return $0$. Otherwise, continue with the next statement.

The grammar for valid expressions is as follows:

• x, y, 0, and 1 are valid expressions.
• If E is a valid expression, then (E) is a valid expression.
• If E is a valid expression, then !E is a valid expression.
• If E1 and E2 are valid expressions, then all strings of the form E1 BIN_OP E2 are valid expressions, where BIN_OP is one of = (equals), & (and), | (or), or ^ (xor).

Parentheses take the highest precedence, followed by the unary !, followed by the binary =, &, |, and ^, in that order. All binary operators are left-associative.

The truth table for the unary operator is shown below.

Figure C.1: The truth table for the sole unary operator.

Figure C.2: Truth tables for the binary operators.

For a function $f(x,y)$ to work as a comparator, it must satisfy certain properties. Informally, it should impose an ordering $<$, where $f(x,y)$ returns $1$ if and only if $x < y$. For example, sample 1 is a valid comparator for bitstrings of length 2. Three of the required properties are the following.

1. Reflexive: For all $x$, $f(x, x)$ returns 0.
2. Symmetric: For all $x,y$, if $f(x, y)$ returns 1, then $f(y, x)$ returns 0.
3. Transitive: For all $x,y,z$, if both $f(x, y)$ and $f(y, z)$ return 1, then $f(x, z)$ returns 1.

Given a function in IFFY, count how often each property is violated. First, among all words of a given length, count the words for which the reflexive property fails. Next, count the pairs of words for which the symmetric property fails. Finally, count the triples of words for which the transitive property fails.

The first line of input contains two integers $n$ ($0 \leq n \leq 2 \cdot 10^{5}$) and $k$ ($1 \leq k \leq 10$), where $n$ is the number of lines in the function and $k$ is the number of bits in the values being compared.

Each of the next $n$ lines contains four tokens of the form a b expr r, where $a$ and $b$ ($1 \leq a, b \leq k$) are the indices of the bits to consider in $x$ and $y$, expr is a valid expression, and $r$ ($0 \leq r \leq 1$) is the return value. The final line gives the returned value if no if statement is triggered. The total length of all expressions is at most $10^6$.

Output a single line with three space-separated integers. The first integer is the number of words for which the reflexive property is violated. The second is the number of pairs of words for which the symmetric property is violated. The third is the number of triples of words for which the transitive property is violated.