A11789. The Moral Dilemma

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.

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$ .

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.

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.