ｆだｓふぁｆ

※ この問題はダウジングの制約が緩和された問題です。
※ この問題でACしたプログラムは、そのままダウジングでもACできます。
※ この問題の難易度は25点で想定しているため、ダウジングとこの問題を合わせて25点がもらえます。

春風遺跡には莫大な財宝が眠っていると噂されています。
これまでの調査で春風遺跡は縦$H$行、横$W$列のマス目状に区切られていることと、このマス目のどこかに財宝が1つ埋まっていることがことが判明しています。
また、このマス目は上から$y$行目、左から$x$列目を$(y, \space x)$と表します。

トレジャーハンターのべーやん君は、財宝の方角を知ることができるダウンジングという超能力を持っており、この力を使って財宝を探しています。
この超能力は発動したマスから見て、財宝が埋まっているマスの方角$D$をL,R,U,Dのいずれかで知ることができます。
べーやん君が$(b_y, \space b_x)$のマスでダウジングを行った時、得られた方角L,R,U,Dは財宝のマス$(g_y, \space g_x)$が以下の範囲にあることを示しています。

• L → $1 \leq g_y \leq H$,　 $1 \leq g_x < b_x$
• R → $1 \leq g_y \leq H$, 　$b_x < g_x \leq W$
• U → $1 \leq g_y < b_y$,　 $1 \leq g_x \leq W$
• D → $b_y < g_y \leq H$, 　$1 \leq g_x \leq W$

べーやん君はこの遺跡を歩き回りながら$N$回ダウジングを行いました。
$i$回目のダウジングは$(Y_i, \space X_i)$のマスで発動しており、そのときに知覚した方向は$D_i$でした。

財宝が埋まっている可能性があるマスの数を出力してください。

入力

1行目に春風遺跡の縦のマスの数$H$、横のマスの数$W$、べーやん君がダウジングを行った回数$N$が空白区切りで与えられる。
続く$N$行に、べーやん君がダウンジングを行った座標$Y_i$、$X_i$、財宝の方角$D_i$が半角区切りで与えられる。

出力

財宝が埋まっている可能性があるマスの数を1行で表示してください。

制約

$1 \leq H, \space W \leq 10^9$
$1 \leq N \leq 10^5$
$1 \leq X_i \leq W$
$1 \leq Y_i \leq H$
$D_i \in {L, R, U, D}$ 　($D_i$はL,R,U,Dのいずれか)
財宝は1つだけ存在しており、$H \times W$マスのいずれか1マスに埋まっている
答えは必ず1つの面積1以上の長方形になる。
財宝が埋まっているマスでダウジングすることは無い