有天知知想约小Q看电影，知知有N件衣服，M条裤子，K双鞋子，他决定好好打扮下自己。可是有些衣服和裤子以及裤子和鞋子的组合，让小Q不愿意跟他走在一起。

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

第一行四个整数N,M,K,P。其中N,M,K为题目描述中的变量，P表示有多少种组合是小Q不喜欢的。接下来P行，每行为“CP x y”表示小Q不喜欢的第x件衣服和第y件裤子组合,或者“PS y z”(表示小Q不喜欢的第y条裤子和第z双鞋子组合)。

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

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

【样例输入2】

2 2 2 2

CP 1 1

PS 1 1

【样例输出2】

5

【样例解释】

样例1：可以随意搭配。

样例2：(衣服,裤子,鞋子)合法搭配方案是：(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]

另有10%的数据，P=0

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

GYF2025