该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

有天小 Z 想约小 Y 看电影，小 Z 有 $N$ 件衣服，$M$ 条裤子，$K$ 双鞋子，衣服，裤子，鞋子的编号都从 $1$ 开始，他决定好好打扮下自己。可是有 $P$ 种衣服和裤子以及裤子和鞋子的组合，让小 Y 不愿意跟他走在一起。不喜欢的组合会以如下两种方式给出：

1. "CP x y" 表示小 Y 不喜欢的第 $x$ 件衣服和第 $y$ 件裤子组合。
2. "PS y z" 表示小 Y 不喜欢的第 $y$ 条裤子和第 $z$ 双鞋子组合。

现在请你帮小 Z 算算，有多少种穿着方案是小 Y 满意的。

• 注意，穿着方案指的是小 Z 选择穿衣服、裤子和鞋子三个组合的方案。

输入格式

第一行四个整数 $N,M,K,P$。其中 $N,M,K$ 为题目描述中的变量，$P$ 表示有多少种组合是小 $Y$ 不喜欢的。

接下来 $P$ 行，每行为 "CP x y" 表示小 Y 不喜欢的第 $x$ 件衣服和第 $y$ 件裤子组合,或者 "PS y z" 表示小 Y 不喜欢的第 $y$ 条裤子和第 $z$ 双鞋子组合。

数据保证，不喜欢的组合不会重复出现。编号从 $1$ 开始。

输出格式

输出小 Z 喜欢的衣服、裤子和鞋子的组合方案数量。

输入输出样例

2 2 2 0

8

2 2 2 2
CP 1 1
PS 1 1

5

见附件

见附件

提示

【样例 1 解释】

没有任何限制，小 Z 可以随便穿，所以合法方案数为 $2*2*2=8$。

【样例 2 解释】

小 Y 不喜欢衣服 $1$ 和 裤子 $1$ 的搭配，以及裤子 $1$ 和鞋子 $1$ 的搭配，那么 小 Z 可以选择的合法方案为 $\{1,2,1\},\{1,2,2\},\{2,1,2\},\{2,2,1\},\{2,2,2\}$，其中三项分别表示衣服、裤子和鞋子的编号。

【数据范围】

对于 $30\%$ 的数据，$N,M,K$ 的范围是$[0,300]$, $P$ 的范围是 $[0,300]$。

对于 $60\%$ 的数据，$N,M,K$ 的范围是 $[0,3000]$, $P$ 的范围是 $[0,10000]$。

对于 $100\%$ 的数据，$N,M,K$ 的范围是 $[0,100000]$, $P$ 的范围是 $[0,100000]$。