奶茶配方

题目描述

你经营一家网红奶茶店，现在店内精心准备了 $a$ 种基底茶（如茉莉绿茶、高山乌龙）、$b$ 种小料（如波霸、弹弹冻）、$c$ 种奶盖（如原味奶盖、芝士奶盖），所有不同种类的基底茶、小料、奶盖的编号均从 $1$ 计数。

一杯口感丰富的奶茶必须要由 $1$ 种基底茶 + $1$ 种小料 + $1$ 种奶盖搭配在一起，若任一成分缺失则无法制作出奶茶。

你向来注重顾客的反馈，经过长期的口味调研你发现，有些搭配存在天然的风味冲突，比如茉莉绿茶配巧克力爆珠会显得口感割裂。目前已知的冲突搭配有 $k$ 种：

• K1 x y：代表第 $x$ 种基底茶和第 $y$ 种小料搭配冲突
• K2 y z：代表第 $y$ 种小料和第 $z$ 种奶盖搭配冲突

为了给顾客提供最佳的饮用体验，你需要统计：目前店内共有多少种无口味冲突、符合顾客口味的完整的奶茶配方？

输入格式

第一行四个整数 $a, b, c, k$，分别代表基底茶、小料、奶盖的种类数以及冲突搭配的数目

接下来的 $k$ 行，每行用一个字符串、两个整数来描述一组冲突搭配，中间用空格间隔，即 K1 x y 或 K2 y z

输出格式

一行一个整数表示答案

输入输出样例

输入 #1

2 2 2 2
K1 1 1
K2 1 1

输出 #1

5

输入 #2

5 2 2 3
K1 3 1
K2 2 1
K2 1 2

输出 #2

9

样例解释

对于样例 $1$，合法的配方有 $5$ 种：

• $\{1,2,1\}, \{1,2,2\}, \{2,1,2\}, \{2,2,1\}, \{2,2,2\}$

对于样例 $2$，合法的配方有 $9$ 种：

• $\{1,1,1\}, \{1,2,2\}, \{2,1,1\}, \{2,2,2\}, \{3,2,2\}, \{4,1,1\}, \{4,2,2\}, \{5,1,1\}, \{5,2,2\}$

数据范围

对于所有测试数据，保证：$0\le a,b,c,k\le 10^5$，所有冲突的搭配不会重复出现