비교 함수

많은 프로그래밍 언어에서는 사용자 정의 객체를 정렬하려고 직접 비교 함수를 정의할 수 있다.

IFFY는 프로그램이 모두 비교 함수인 프로그래밍 언어다. 이 함수들은 비트열("단어"라고 부른다)에 대해 동작한다. 단어의 번호는 1부터 시작하며, 가장 왼쪽 문자가 1번이다.

IFFY에서 두 단어를 받는 함수는 if 문을 여러 개 나열해서 작성한다. 각 if 문은 첫 번째 단어에서 비트 하나, 두 번째 단어에서 비트 하나를 고르고, 그 두 비트에 대해 식을 계산한다. 선택한 비트에 대해 식의 값이 1이면 함수는 지정된 반환값을 바로 돌려준다. 그렇지 않으면 실행이 다음 if 문으로 넘어간다.

각 if 문의 형식은 a b expr r이다. 정수 $a$는 첫 번째 단어의 비트를, 정수 $b$는 두 번째 단어의 비트를 가리킨다. expr은 변수 x와 y를 사용하는 불리언 식이고, $r$은 식이 1일 때 반환하는 값($0$ 또는 $1$)이다. x는 첫 번째 단어에서 고른 비트를, y는 두 번째 단어에서 고른 비트를 나타낸다. 예를 들어 2 3 x|y 0은 첫 번째 단어의 2번째 비트나 두 번째 단어의 3번째 비트가 1이면 $0$을 반환한다는 뜻이다. 그렇지 않으면 다음 문장으로 넘어간다.

올바른 식의 문법은 다음과 같다.

• x, y, 0, 1은 올바른 식이다.
• $E$가 올바른 식이면 (E)도 올바른 식이다.
• $E$가 올바른 식이면 !E도 올바른 식이다.
• $E1$과 $E2$가 올바른 식이면, E1 BIN_OP E2 형태의 문자열은 모두 올바른 식이다. 여기서 BIN_OP는 =(같음), &(그리고), |(또는), ^(배타적 또는) 중 하나다.

우선순위는 괄호가 가장 높고, 다음이 단항 !, 그다음이 이항 =, &, |, ^의 순서다. 모든 이항 연산자는 왼쪽 결합이다.

단항 연산자의 진리표는 다음과 같다.

그림 C.1: 단항 연산자의 진리표.

그림 C.2: 이항 연산자의 진리표.

함수 $f(x,y)$가 비교 함수로 동작하려면 몇 가지 성질을 만족해야 한다. 직관적으로 $f(x,y)$는 $x < y$일 때에만 1을 반환해야 하며, 그러한 순서 $<$를 정의해야 한다. 예를 들어 샘플 1은 길이 2인 비트열을 정렬하는 올바른 비교 함수다. 필요한 성질 중 세 가지는 다음과 같다.

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 \leq n \leq 2 \cdot 10^{5}$)과 $k$($1 \leq k \leq 10$)가 주어진다. $n$은 함수의 줄 수이고, $k$는 비교할 값의 비트 수다.

이어지는 $n$개의 줄에는 각각 a b expr r 형태의 토큰 네 개가 있다. $a$와 $b$($1 \leq a, b \leq k$)는 $x$와 $y$에서 고려할 비트의 번호이고, expr은 올바른 식이며, $r$($0 \leq r \leq 1$)은 반환값이다. 마지막 줄에는 어떤 if 문도 실행되지 않았을 때의 반환값이 주어진다. 모든 식의 길이 합은 최대 $10^6$이다.

세 개의 정수를 공백으로 구분해 한 줄에 출력한다. 첫 번째 정수는 반사성이 깨지는 단어의 수, 두 번째 정수는 대칭성이 깨지는 단어 쌍의 수, 세 번째 정수는 추이성이 깨지는 단어 세 쌍의 수다.