Problem Description

Many programming languages allow custom comparators for sorting user-defined objects.

In the fictional language IFFY, every program is a comparator over two bitstrings (called words).
Words are 1-indexed from left to right.

An IFFY program is a sequence of if-statements.
Each statement has the form:

a b expr r

where:

• a is the index of a bit chosen from the first word,
• b is the index of a bit chosen from the second word,
• expr is a Boolean expression involving variables x and/or y,
• r is the return value (0 or 1) if the expression evaluates to 1.

Here:

• x denotes the chosen bit from the first word,
• y denotes the chosen bit from the second word.

The function evaluates the if-statements in order.
As soon as one expression evaluates to 1, the function immediately returns r.
If no if-statement triggers, the function returns the value given on the last line of the input.

For example, the line

2 3 x|y 0

means: look at the second bit of the first word and the third bit of the second word; if x OR y = 1, then return 0, otherwise continue.

Expression Grammar

Valid expressions are defined recursively:

• x, y, 0, and 1 are valid expressions.
• If E is valid, then (E) is valid.
• If E is valid, then !E is valid.
• If E1 and E2 are valid, then E1 BIN_OP E2 is valid, where BIN_OP is one of:
  • = : equality
  • & : and
  • | : or
  • ^ : xor

Operator Precedence

From highest to lowest:

1. Parentheses
2. Unary !
3. Binary =
4. Binary &
5. Binary |
6. Binary ^

All binary operators are left-associative.

Truth Tables

Unary Operator

Binary Operators

Equality =

And &

Or |

Xor ^

Comparator Properties

Let f(x, y) be the comparator result for two words x and y.
A proper comparator should represent an ordering <, meaning f(x, y) = 1 exactly when x < y.

You must count violations of these three properties:

1. Reflexive condition: for all x, f(x, x) should return 0.
2. Symmetric condition: for all x, y, if f(x, y) = 1, then f(y, x) must be 0.
3. Transitive condition: for all x, y, z, if f(x, y) = 1 and f(y, z) = 1, then f(x, z) must also be 1.

Task

Given an IFFY comparator and a fixed word length k, compute:

• the number of words for which the reflexive condition fails,
• the number of ordered pairs of words for which the symmetric condition fails,
• the number of ordered triples of words for which the transitive condition fails.

Input

The first line contains two integers n and k:

• 0 <= n <= 2 * 10^5
• 1 <= k <= 10

where:

• n is the number of if-statements,
• k is the length of the bitstrings being compared.

Each of the next n lines contains four tokens of the form:

a b expr r

with:

• 1 <= a, b <= k
• expr a valid expression
• r equal to 0 or 1

The final line contains the return value used if no if-statement triggers.

The total length of all expressions is at most 10^6.

Output

Output one line with three space-separated integers:

1. the number of words violating the reflexive condition,
2. the number of pairs violating the symmetric condition,
3. the number of triples violating the transitive condition.

Sample Input 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

Sample Output 1

0 0 0

Sample Input 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

Sample Output 2

3 25 52