Hibiki 和 Dita 彼此相爱,但属于长期冲突的社区。响对事态深感忧虑,并想弄清楚他与蒂塔的关系是爱的行为还是叛国的行为。
Hibiki 准备了他的决定所依赖的几个二进制特征,并在它们之上构建了一个三层逻辑电路,每层由一个或多个逻辑门组成。电路中的每个门要么是“或”、“与”、“nor”(非或)或“nand”(非与)。第一层中的每个门都恰好连接到两个特征。第二层中的每个门恰好连接到第一层中的两个门。第三层只有一个“或”门,它与第二层中的所有门相连(换句话说,当且仅当第二层中至少有一个门产生1时,整个电路才产生1)。
问题是,响很清楚,当一个人陷入爱情时,他的逻辑思考能力会急剧下降。特别是,众所周知,当一个恋爱中的人评估他头脑中的逻辑电路时,每个门都会评估出与它应该评估的值相反的值。例如,“或”门当且仅当两个输入均为 0 时才返回 1,“t{nand}”门当且仅当两个输入均为 1 时才返回 1,等等。
特别是,最后一层的“或”门也会产生相反的结果,因此,如果 Hibiki 恋爱了,当且仅当第二层上的所有门都产生 0 时,整个电路才会产生 1。
响不能让爱情影响他的决定。他想知道需要从第二层移除的门的最小数量是多少,以便所有可能输入的电路输出不取决于 Hibiki 是否恋爱。
输入
第一行包含三个整数 $$$n$$$、$$$m$$$、$$$k$$$ ($$$2 \le n, m \le 50$$$; $$$1 \le k \le 50$$$) — 输入特征的数量、第一层门的数量和第二层门的数量。
第二行包含 $$$m$$$ 字符串对,以空格分隔,描述第一层。每对中的第一个字符串描述门(“and”、“or”、“nand”或“nor”),第二个字符串描述门连接的两个输入特征,作为由 $$$n$$$ 字符组成的字符串,其中恰好有两个字符(对应于门连接到的输入特征)等于“x”,其余字符等于“.”。
第三行包含 $$$k$$$ 字符串对,以空格分隔,以相同的格式描述第二层,其中描述输入参数的字符串长度为 $$$m$$$ 并对应于第一层的门。
输出
打印需要从第二层移除的门的数量,以便剩余电路的输出不取决于 Hibiki 是否恋爱。
如果无论移除多少个门,电路的输出仍然取决于 Hibiki 的感受,则打印 $$$-1$$$。
示例
输入 #1
2 2 2 and xx nand xx and xx or xx
输出 #1
1
输入 #2
3 2 2 and xx. nor .xx and xx nor xx
输出 #2
-1
输入 #3
4 4 5 nor x..x and ..xx and xx.. nand xx.. nand ..xx nor ..xx and xx.. nor ..xx or ..xx
输出 #3
2
注意
在第一个示例中,第一层中的两个门连接到相同的输入,但第一个计算“and”,第二个计算“nand”,因此无论输入是什么以及 Hibiki 是否恋爱,它们的输出总是不同的。第二层具有“或”门和“与”门,均连接到第一层中的两个门。如果 Hibiki 没有恋爱,无论输入特征是什么,“与”门都会产生 0,“或”门都会产生 1,第三层的最终“或”门总是产生最终答案 1。如果 Hibiki 恋爱了,无论输入是什么,第二层的“与”门都会产生 1,“或”门都会产生 0,第三层的最终“或”门产生最终答案 0。因此,如果两个保留第二层的门,电路的输出确实取决于 Hibiki 是否恋爱。如果第二层中的两个门中的任何一个被丢弃,电路的输出将不再取决于 Hibiki 是否恋爱,因此答案为 1。
在第二个例子中,无论第二层留下什么门,电路的输出都将取决于 Hibiki 是否恋爱。
在第三个例子中,如果 Hibiki 在第二层保留第二、第三和第四门,则电路将不依赖于 Hibiki 是否恋爱。或者,他可以保留第一个和最后一个门。前者需要去掉两个门,后者需要去掉三个门,所以前者更好,答案是2。