Nothing But The Truth

When someone shows you a news story, telling a true one from a fake one is hard. It is harder still when the story was written to sound believable to you or to someone with your biases. Sometimes you already know facts that contradict the story. You are given several facts about where several people were at which times, and then a text that claims where those people were and whom they met. Count how many claims in the text are definitely false given the facts.

Every fact has the same form: person X was at place Y from time $t_1$ until time $t_2$, both endpoints included. The same person, the same place and the same time may appear in many facts, but no fact ever puts one person in two places at the same time. At a time for which no fact says where a person was, that person could have been anywhere.

The text claims who met whom and who was where at which times. It makes many other claims too, and you ignore those. The text uses upper case and lower case letters, digits, spaces (including tabs and newlines), periods, commas and hyphens. A period ends a sentence. Inside a sentence every character that is not a letter or a digit separates words, so a word is a maximal run of letters and digits. A sentence can run across several lines. Case does not matter, so Jill and jiLl are the same person and met and mET are the same word.

Two kinds of sentences carry claims.

A sentence that contains the word met claims that every two people named in it met each other, though not necessarily at the same time or in the same place. For example, "Flynn, Trump and Putin met." claims that the pair (Flynn, Trump) met at some point, that (Flynn, Putin) met at some other point, and that (Trump, Putin) met at some point. Each unordered pair of distinct people named in the sentence is one claim. A name that appears several times in the sentence still names one person.

A sentence that contains the two consecutive words was at claims where people were. The word right after that at is the claimed place. The claimed interval is given by the word from followed by an integer and the word until followed by an integer. Both integers are between 0 and 10000, and the from integer is never larger than the until integer. The sentence claims that every person named in it was at that place over the whole interval, endpoints included. For example, "Until 50 Bernie was at Philadelphia Hillary from 30." claims that Bernie was at Philadelphia from time 30 until time 50 and that Hillary was at Philadelphia from time 30 until time 50. Each distinct person named in the sentence is one claim.

No sentence contains both met and was at. No sentence contains was at twice. A sentence that contains was at contains exactly one from and exactly one until, and an integer follows each of them. A sentence without was at may still contain from, until or numbers, and you ignore them. No two people or places have the same name, no person and place share a name, and no person or place is named met, from, until, was, at, or any other word that carries special meaning here.

Whoever wrote the text avoided internal contradictions, such as claiming that Bernie was at Philadelphia from 30 to 50 and at Vermont from 20 to 30, so you do not look for those. You count the false claims instead. In the examples above, if Flynn met Trump but neither Flynn nor Trump met Putin, that is two false claims. If neither Bernie nor Hillary was at Philadelphia for the whole interval 30 to 50 (say Hillary was there from 30 to 45 and Bernie from 40 to 50), that is two false claims as well.

A claim that X met Y is true when the facts put the two at the same place at the same time at least once. Sharing a single instant is enough: if Flynn was at MarALago from 10 to 20 and Trump was at MarALago from 20 to 22, they met. Written out, the claim is true when some fact puts X at a place P over $[s_1, f_1]$, some fact puts Y at the same place P over $[s_2, f_2]$, and $s_1 \le f_2$ and $s_2 \le f_1$. Without such evidence the claim is false.

A claim that person X was at place Y from $t_1$ until $t_2$ is false only when the facts show X somewhere else for at least one time unit inside that interval, that is, when some fact puts X at a place $Z$ other than Y over $[s, f]$ with $\min(f, t_2) - \max(s, t_1) \ge 1$. An overlap of a single instant does not make the claim false, and neither does a time inside the interval for which you know nothing.

The first line contains the number of data sets $K \ge 1$. Then come $K$ data sets in the following form.

The first line of a data set has four integers $p$, $\ell$, $m$, $n$. $1 \le p \le 20$ is the number of people, $1 \le \ell \le 20$ is the number of places, $0 \le m \le 1000$ is the number of facts, and $0 \le n \le 30$ is the number of lines of text.

The next line has the names of the $p$ people, separated by spaces or tabs. Each name is a string of 1 to 16 letters and has no space in it. The line after that has the names of the $\ell$ places in the same form.

Then come $m$ lines, each giving one fact as four integers $p_i$, $\ell_i$, $s_i$, $f_i$. $1 \le p_i \le p$ is the person, $1 \le \ell_i \le \ell$ is the place, and $0 \le s_i \le f_i \le 10000$ is the interval during which person $p_i$ was at place $\ell_i$, from $s_i$ until $f_i$ inclusive.

Finally come $n$ lines of the text described above. Each line holds at most 120 characters and may be empty.

For each data set, print Data Set x: on a line of its own, where x is the number of the data set counting from 1. On the next line print the number of false claims in its text. Print a blank line after each data set.