Nothing But The Truth

누군가 뉴스 기사를 보여 주면 그것이 진짜인지 가짜인지 가려내기 어렵다. 읽는 사람의 편향에 맞춰 그럴듯하게 쓴 기사라면 더 그렇다. 하지만 기사와 어긋나는 사실을 이미 알고 있다면 이야기가 달라진다. 여러 사람이 어느 시각에 어디 있었는지 알려 주는 사실 몇 개와, 그 사람들이 어디 있었고 누구를 만났는지 주장하는 글이 주어진다. 주어진 사실에 비추어 확실히 거짓인 주장이 글에 몇 개 들어 있는지 세어라.

사실은 모두 사람 X가 시각 $t_1$부터 시각 $t_2$까지 장소 Y에 있었다는 형태이고 양 끝 시각을 포함한다. 같은 사람, 같은 장소, 같은 시각이 여러 사실에 나올 수 있지만, 한 사람이 같은 시각에 서로 다른 두 장소에 있었다고 알려 주는 사실은 없다. 어떤 사람이 어디 있었는지 알려 주지 않은 시각에는 그 사람이 어디에나 있을 수 있다.

글은 누가 누구를 만났는지, 누가 언제 어디 있었는지 주장한다. 그 밖의 주장도 많이 하지만 그런 주장은 무시한다. 글에는 영문 대소문자, 숫자, 공백(탭과 줄바꿈 포함), 마침표, 쉼표, 붙임표가 쓰인다. 마침표는 문장을 끝낸다. 문장 안에서는 영문자와 숫자가 아닌 모든 문자가 단어를 나눈다. 즉 단어는 영문자와 숫자가 이어진 최대 구간이다. 한 문장이 여러 줄에 걸칠 수 있다. 대소문자는 구분하지 않으므로 Jill과 jiLl은 같은 사람이고 met과 mET은 같은 단어다.

주장을 담은 문장은 두 종류다.

met이라는 단어가 있는 문장은 그 문장에 이름이 나온 사람들이 서로 만났다고 주장한다. 같은 시각이거나 같은 장소일 필요는 없다. 예를 들어 "Flynn, Trump and Putin met."은 (Flynn, Trump)가 어느 시점에 만났고, (Flynn, Putin)이 또 다른 시점에 만났고, (Trump, Putin)이 어느 시점에 만났다고 주장한다. 문장에 이름이 나온 서로 다른 두 사람의 순서 없는 쌍 하나가 주장 하나다. 한 이름이 여러 번 나와도 사람은 하나로 센다.

was at 두 단어가 이어서 나오는 문장은 사람이 어디 있었는지 주장한다. 그 at 바로 다음 단어가 주장하는 장소다. 주장하는 시간 구간은 from 다음의 정수와 until 다음의 정수로 정해진다. 두 정수는 모두 0 이상 10000 이하이고 from 쪽 정수가 until 쪽 정수보다 크지 않다. 이 문장은 이름이 나온 모든 사람이 그 구간 내내, 양 끝 시각을 포함해 그 장소에 있었다고 주장한다. 예를 들어 "Until 50 Bernie was at Philadelphia Hillary from 30."은 Bernie가 시각 30부터 50까지 Philadelphia에 있었고 Hillary도 시각 30부터 50까지 Philadelphia에 있었다고 주장한다. 문장에 이름이 나온 사람 한 명이 주장 하나다.

한 문장에 met과 was at이 함께 나오지 않는다. 한 문장에 was at이 두 번 나오지 않는다. was at이 있는 문장에는 from과 until이 정확히 한 번씩 나오고 둘 다 바로 뒤에 정수가 온다. was at이 없는 문장에도 from이나 until, 숫자가 나올 수 있고 그런 것은 무시한다. 이름이 같은 사람이나 장소는 없고, 사람과 장소가 이름을 공유하지도 않으며, met, from, until, was, at처럼 특별한 뜻을 가진 단어를 이름으로 쓰는 사람이나 장소도 없다.

글을 쓴 쪽은 Bernie가 30부터 50까지 Philadelphia에 있었다고 하면서 20부터 30까지 Vermont에 있었다고 하는 식의 자체 모순은 피했으므로 그런 모순은 찾지 않는다. 대신 거짓인 주장의 개수를 센다. 위 예에서 Flynn과 Trump는 만났지만 Flynn도 Trump도 Putin을 만나지 않았다면 거짓 주장이 둘이다. Bernie도 Hillary도 30부터 50까지 내내 Philadelphia에 있지는 않았다면(Hillary는 30부터 45까지, Bernie는 40부터 50까지 있었다면) 이 역시 거짓 주장이 둘이다.

X가 Y를 만났다는 주장은 두 사람이 같은 장소에 같은 시각에 적어도 한 번 있었다는 사실이 있으면 참이다. 한 순간만 겹쳐도 충분해서, Flynn이 10부터 20까지 MarALago에 있었고 Trump가 20부터 22까지 MarALago에 있었다면 둘은 만났다. 식으로 쓰면 어떤 사실이 X를 장소 P에 $[s_1, f_1]$ 동안 두고 어떤 사실이 Y를 같은 장소 P에 $[s_2, f_2]$ 동안 두면서 $s_1 \le f_2$이고 $s_2 \le f_1$이면 참이다. 그런 근거가 없으면 거짓이다.

사람 X가 $t_1$부터 $t_2$까지 장소 Y에 있었다는 주장은, 그 구간 안에서 X가 다른 곳에 시간 단위로 1 이상 머물렀다는 근거가 있을 때만 거짓이다. 즉 어떤 사실이 X를 Y와 다른 장소 $Z$에 $[s, f]$ 동안 두고 $\min(f, t_2) - \max(s, t_1) \ge 1$이면 거짓이다. 한 순간만 겹치는 것으로는 거짓이 되지 않고, 알지 못하는 시각이 구간 안에 있다고 해서 거짓이 되지도 않는다.

첫 줄에 데이터 집합의 개수 $K \ge 1$이 주어진다. 이어서 다음 형식의 데이터 집합이 $K$개 주어진다.

데이터 집합의 첫 줄에는 정수 네 개 $p$, $\ell$, $m$, $n$이 있다. $1 \le p \le 20$은 사람 수, $1 \le \ell \le 20$은 장소 수, $0 \le m \le 1000$은 주어지는 사실의 개수, $0 \le n \le 30$은 글의 줄 수다.

다음 줄에는 사람 $p$명의 이름이 공백이나 탭으로 구분되어 주어진다. 각 이름은 길이 1 이상 16 이하의 영문자 문자열이고 이름 안에 공백은 없다. 그다음 줄에는 장소 $\ell$개의 이름이 같은 형식으로 주어진다.

이어서 $m$개 줄에 사실이 하나씩 정수 네 개 $p_i$, $\ell_i$, $s_i$, $f_i$로 주어진다. $1 \le p_i \le p$는 사람, $1 \le \ell_i \le \ell$은 장소, $0 \le s_i \le f_i \le 10000$은 사람 $p_i$가 장소 $\ell_i$에 있었던 구간이며 $s_i$부터 $f_i$까지 양 끝을 포함한다.

마지막으로 위에서 설명한 글이 $n$개 줄로 주어진다. 각 줄은 120자 이하이고 빈 줄일 수도 있다.

각 데이터 집합마다 먼저 Data Set x:를 한 줄에 출력한다. x는 1부터 세는 데이터 집합의 번호다. 다음 줄에 그 글에 들어 있는 거짓 주장의 개수를 출력한다. 각 데이터 집합 뒤에는 빈 줄을 하나 출력한다.