[Apio2012]kunai

广场由从左到右编号为 $1$ 到 $W$ 的列和从上到下编号为 $1$ 到 $H$ 的行组成，每个格子都是边长为 $1$ 的单位正方形。$N$ 名忍者分别站在互不相同的格子中心，并在时刻 $0$ 同时沿各自面向的方向投出一枚苦无。

所有苦无均沿水平或竖直方向做直线运动，速度为每单位时间移动一个格子的边长。当至少 $2$ 枚仍在运动的苦无在同一时刻到达同一位置时，它们会立即同时消失。碰撞位置既可能位于格子中心，也可能位于相邻格子的公共边界上。苦无飞出广场后不再产生影响。

如果一枚苦无在消失或飞出广场之前进入过某个格子的内部，则称该格子被苦无经过。忍者所在的起始格也视为被经过。如果苦无恰好在两个相邻格子的公共边界处发生碰撞，则仅接触该边界不视为进入边界另一侧的格子。

求经过足够长时间后，广场中至少被一枚苦无经过的不同格子数量。

输入格式

第一行包含两个用空格分隔的整数 $W,H$，表示广场共有 $W$ 列、$H$ 行。

第二行包含一个整数 $N$，表示忍者的数量。

接下来 $N$ 行，第 $i$ 行包含三个用空格分隔的整数 $X_i,Y_i,D_i$，表示第 $i$ 名忍者位于从左到右的第 $X_i$ 列、从上到下的第 $Y_i$ 行。任意两名忍者的位置均不相同。

$D_i$ 表示第 $i$ 名忍者面向的方向：

• $D_i=0$，表示向右；
• $D_i=1$，表示向上；
• $D_i=2$，表示向左；
• $D_i=3$，表示向下。

输出格式

输出一个整数，表示经过足够长时间后，广场中至少被一枚苦无经过的不同格子数量。

样例输入

5  4
5
3  3 2
3  2 0
4  2 2
5  4 1
1  1 3

样例输出

11

数据范围

• $1\le N\le 10^5$；
• $1\le W\le 10^9$；
• $1\le H\le 10^9$；
• $1\le X_i\le W$，$1\le Y_i\le H$。

来源与许可

本题为 APIO 2012 试题「Kunai」，题面与测试数据整理自 BZOJ。

样例 1

输入

5  4
5
3  3 2
3  2 0
4  2 2
5  4 1
1  1 3

输出

11