CF993F.The Moral Dilemma

Hibiki and Dita are in love with each other, but belong to communities that are in a long lasting conflict. Hibiki is deeply concerned with the state of affairs, and wants to figure out if his relationship with Dita is an act of love or an act of treason.

Hibiki prepared several binary features his decision will depend on, and built a three layer logical circuit on top of them, each layer consisting of one or more logic gates. Each gate in the circuit is either "or", "and", "nor" (not or) or "nand" (not and). Each gate in the first layer is connected to exactly two features. Each gate in the second layer is connected to exactly two gates in the first layer. The third layer has only one "or" gate, which is connected to all the gates in the second layer (in other words, the entire circuit produces 1 if and only if at least one gate in the second layer produces 1).

The problem is, Hibiki knows very well that when the person is in love, his ability to think logically degrades drastically. In particular, it is well known that when a person in love evaluates a logical circuit in his mind, every gate evaluates to a value that is the opposite of what it was supposed to evaluate to. For example, "or" gates return 1 if and only if both inputs are zero, "t{nand}" gates produce 1 if and only if both inputs are one etc.

In particular, the "or" gate in the last layer also produces opposite results, and as such if Hibiki is in love, the entire circuit produces 1 if and only if all the gates on the second layer produced 0.

Hibiki can’t allow love to affect his decision. He wants to know what is the smallest number of gates that needs to be removed from the second layer so that the output of the circuit for all possible inputs doesn't depend on whether Hibiki is in love or not.

Hibiki 和 Dita 彼此相爱，却分别属于长期处于冲突状态的两个社群。Hibiki 对当前局势深感忧虑，他想弄清楚：自己与 Dita 的这段感情，究竟是一种爱的表达，还是一种叛国行为？

Hibiki 事先准备了若干个二元特征（binary features），并在此基础上构建了一个三层逻辑电路，每一层均由一个或多个逻辑门组成。电路中每个门只能是 “OR”（或）、“AND”（与）、“NOR”（或非，即 NOT OR）或 “NAND”（与非，即 NOT AND）。第一层的每个门恰好连接两个输入特征；第二层的每个门恰好连接第一层中的两个门；第三层仅含一个 “OR” 门，它连接第二层的所有门（换言之，整个电路输出为 1 当且仅当第二层中至少有一个门输出为 1）。

问题在于：Hibiki 非常清楚，当一个人陷入爱河时，其逻辑思维能力会急剧退化。具体而言，众所周知：当一个处于热恋中的人在脑海中评估一个逻辑电路时，每个门的输出值都与其本应输出的值相反。例如，“OR” 门当且仅当两个输入均为 0 时输出 1；“NAND” 门当且仅当两个输入均为 1 时输出 1，等等。

特别地，最后一层的 “OR” 门同样会产生相反的结果；因此，若 Hibiki 处于热恋中，整个电路输出为 1 当且仅当第二层所有门均输出 0。

Hibiki 不允许爱情干扰自己的判断。他想知道：至少需要从第二层中移除多少个门，才能使得该电路对所有可能输入的输出结果，都不再依赖于 Hibiki 是否处于热恋之中？

The first line contains three integers $n$, $m$, $k$ ($2 \le n, m \le 50$; $1 \le k \le 50$) — the number of input features, the number of gates in the first layer, and the number of gates in the second layer correspondingly.

The second line contains $m$ pairs of strings separated by spaces describing the first layer. The first string in each pair describes the gate ("and", "or", "nand" or "nor"), and the second string describes the two input features the gate is connected two as a string consisting of exactly $n$ characters, with exactly two characters (that correspond to the input features the gate is connected to) equal to 'x' and the remaining characters equal to ".'.

The third line contains $k$ pairs of strings separated by spaces describing the second layer in the same format, where the strings that describe the input parameters have length $m$ and correspond to the gates of the first layer.

第一行包含三个整数 $n$、$m$、$k$（$2 \le n, m \le 50$；$1 \le k \le 50$），分别表示输入特征的数量、第一层中的门电路数量以及第二层中的门电路数量。

第二行包含 $m$ 对由空格分隔的字符串，用于描述第一层。每对字符串中，第一个字符串表示门类型（"and"、"or"、"nand" 或 "nor"），第二个字符串表示该门所连接的两个输入特征，其为一个长度恰好为 $n$ 的字符串，其中恰好有两个字符（对应于该门所连接的输入特征）为 'x'，其余字符均为 '.'。

第三行以相同格式包含 $k$ 对由空格分隔的字符串，用于描述第二层，其中描述输入参数的字符串长度为 $m$，且对应于第一层中的门电路。

Print the number of gates that need to be removed from the second layer so that the output of the remaining circuit doesn't depend on whether Hibiki is in love or not.

If no matter how many gates are removed the output of the circuit continues to depend on Hibiki's feelings, print $-1$.

打印需要从第二层移除的逻辑门数量，使得剩余电路的输出不再依赖于日比基是否陷入爱河。

如果无论移除多少个逻辑门，电路的输出始终依赖于日比基的感情状态，则输出 $-1$。

In the first example the two gates in the first layer are connected to the same inputs, but first computes "and" while second computes "nand", and as such their output is always different no matter what the input is and whether Hibiki is in love or not. The second layer has "or" and "and" gates both connected to the two gates in the first layer. If Hibiki is not in love, the "and" gate will produce 0 and the "or" gate will produce 1 no matter what input features are equal to, with the final "or" gate in the third layer always producing the final answer of 1. If Hibiki is in love, "and" gate in the second layer will produce 1 and "or" gate will produce 0 no matter what the input is, with the final "or" gate in the third layer producing the final answer of 0. Thus, if both gates in the second layer are kept, the output of the circuit does depend on whether Hibiki is in love. If any of the two gates in the second layer is dropped, the output of the circuit will no longer depend on whether Hibiki is in love or not, and hence the answer is 1.

In the second example no matter what gates are left in the second layer, the output of the circuit will depend on whether Hibiki is in love or not.

In the third example if Hibiki keeps second, third and fourth gates in the second layer, the circuit will not depend on whether Hibiki is in love or not. Alternatively, he can keep the first and the last gates. The former requires removing two gates, the latter requires removing three gates, so the former is better, and the answer is 2.

在第一个例子中，第一层的两个门都连接到相同的输入，但第一个门计算“与”（AND），第二个门计算“与非”（NAND），因此无论输入为何、无论日比基是否恋爱，它们的输出总是互异。第二层包含一个“或”（OR）门和一个“与”（AND）门，二者均连接至第一层的两个门。若日比基未恋爱，则第二层的“与”门输出恒为 0，而“或”门输出恒为 1（无论输入特征取何值），从而第三层的最终“或”门恒输出最终结果 1；若日比基正在恋爱，则第二层的“与”门输出恒为 1，而“或”门输出恒为 0（无论输入为何），从而第三层的最终“或”门恒输出最终结果 0。因此，若第二层两个门均被保留，则电路输出确实依赖于日比基是否恋爱；若第二层任意一个门被移除，则电路输出将不再依赖于日比基是否恋爱，故答案为 1。

在第二个例子中，无论第二层保留哪些门，电路输出始终依赖于日比基是否恋爱。

在第三个例子中，若日比基在第二层保留第 2、第 3 和第 4 个门，则电路输出将不再依赖于日比基是否恋爱；另一种方案是仅保留第 1 和第 5 个门。前者需移除 2 个门，后者需移除 3 个门，因此前者更优，故答案为 2。