wwx 的传送门plus

题目描述

众所周知 wwx 很喜欢玩一款名为 《传送门》 的游戏，在游戏中，玩家会获得一把传送枪，在任意位置可以打出传送门，当打出两个传送门时，这两个传送门将会连通，以此来完成一些任务或者穿越一些障碍

而这个游戏最近出了一个新的模式——定点传送模式

在这个模式下，玩家将会进入到一个 $n * m$ 的迷宫中，这个迷宫共有 $n * m$ 个房间，并且房间之间完全堵死，无法同行

在这些迷宫中，将会存在 $k$ 个地点拥有传送门，并且在这个模式下，将会有三种特殊的传送门用编号 $A,B,C$ 表示

若 $(x,y)$ 这个房间的是 $A$ 类传送门，则可以传送到周围一圈的房间，即 $(上，下，左，右，左上，右上，左下，右下)$ 若 $(x,y)$ 这个房间的是 $B$ 类传送门，则可以传送到 $(x,i)$ 房间，其中 $1 \leq i \leq m$ 若 $(x,y)$ 这个房间的是 $C$ 类传送门，则可以传送到 $(i,y)$ 房间，其中 $1 \leq i \leq n$

注意，所有的传送门均是单向传送

现在 wwx 想知道，如果她可以任选一个房间作为起点，她最多可以使用多少个传送门？

这里我们认为：一个传送门可以重复使用，一个房间可以重复到达，但是重复使用同一个传送门只计算一次答案

输入格式

输入第一行包含三个整数 $n,m,k$ 表示地图大小及传送门数量

接下来 $k$ 行，每行用形如 $x_i,y_i,z_i$ 的形式表示一个传送门在 $(x_i,y_i)$ 处，种类为 $z_i \in [A,B,C]$

输出格式

输出一个数字表示 wwx 最多能使用的传送门数量

数据范围

数据点

$n,m$

$k$

$1$

$n=m=20$

$k=16$

$2$

$n=m=1000$

$k=300$

$3$

$n=m=10^5$

$k=500$

$4$

$n=m=5000$

$k=2500$

$5$

$k=50000$

$6$

$n=m=10^6$

$7$

$k=80000$

$8 \sim 10$

$k=10^5$

对于所有的数据保证同一个地点不会有多个传送门

样例输入

7 7 10
2 2 B
2 4 C
1 7 C
2 7 A
4 2 C
4 4 B
6 7 A
7 7 B
7 5 C
5 2 B

样例输出

9