0006 - クナイ

クナイとは，忍者の使用したナイフのような武器である．忍者たちはクナイを投げて攻撃を行っていた．横 W × 縦 H のマス目に N 人の忍者がいる．

全ての忍者はマスの中央におり，どの 2 人の忍者も同じマスにいない．それぞれの忍者はクナイを 1 個ずつ持っており，上下左右いずれかの方向を向いている．時刻 0 に，全ての忍者はいっせいに自分の向いている方向にクナイを投げた．

全てのクナイは速度 1 で向いている方向に進む．複数のクナイが同時に同じ地点に達すると，それらのクナイは衝突し消滅する．クナイの大きさは無視できるほど小さい．また，忍者はとても素早いので，クナイに当たることはない．クナイは他のクナイと衝突しない限り，向いている方向に失速することなく飛 び続ける．

以下の図において，矢印はクナイを，矢印の方向はクナイの飛んでいる方向を表す．下の図それぞれで，太い矢印で表したクナイ同士は全て衝突する．

一方，下の図それぞれで，太い矢印で表したクナイ同士は衝突しない．2 番目の図と 3 番目の図において，細い矢印で表したクナイと太い矢印で表したクナイが先に衝突し，消滅するため，太い矢印で表したクナイ同士は衝突しない．

制限

入力

標準入力から以下の入力を読み込め．

• 1 行目には整数 W, H が空白区切りで書かれており，マス目の大きさを表す．
• 2 行目には整数 N が書かれており，忍者の人数を表す
• 続く N 行のうち i 行目 (1 ≦ i ≦ N) には，3 つの整数 X_i, Y_i, D_i が空白を区切りとして書かれている．X_i, Y_i は，忍者 i が左から X_i 番目，上から Y_i 番目のマスにいることを表す．どの異なる 2 人の忍者も 同じマスにいない．D_i は忍者 i の向いている方向を表す．
  • D_i = 0 の場合は忍者 i が右を向いていることを表す．
  • D_i = 1 の場合は忍者 i が上を向いていることを表す．
  • D_i = 2 の場合は忍者 i が左を向いていることを表す．
  • D_i = 3 の場合は忍者 i が下を向いていることを表す．

出力

十分時間が経ったとき，W × H のマス目でクナイの通過したマスの数を一行で出力せよ．

採点基準

採点用データのうち，配点の 10%分については，N ≦ 1 000, W ≦ 1 000, H ≦ 1 000 を満たす．

採点用データのうち，配点の 40%分については，N ≦ 1 000 を満たす．

入出力の例

入力例1

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

出力例1

11

この入力例で，時刻 0 におけるマス目の状態を以下の図で示す．

忍者 i の投げたクナイをクナイ i と書くことにする．時刻 0.5 に，クナイ 2 とクナイ 3 が衝突し，消滅する．時刻 1 におけるマス目の状態を以下の図で示す．ただし，灰色のマスは既にクナイの通過したマスを表す．

時刻 2 に，クナイ 1 とクナイ 5 が衝突し，消滅する．時刻 2 におけるマス目の状態を以下の図で示す．

時刻 2 より後にクナイ同士がマス目内で衝突することはない．十分時間が経った後のマス目の状態を以下の図で示す．

クナイがマス目内で通過したマスの数は 11 であるので，11 を出力する．

入力例2

7 6
12
3 2 3
6 3 2
7 1 3
1 5 0
3 6 1
6 6 1
4 5 2
1 3 0
6 5 2
5 1 2
6 4 3
4 1 3

出力例2

29