この問題は「Treasure Searching Rod (Hard)」と同じ設定の問題で，制約のみが異なります．

問題文

$H$ 行 $W$ 列のマス目があり，$i$ 行 $j$ 列目のマスを $(i,j)$ で表します．

このマス目の中の $K$ マスには，「宝」が $10^{100}$ 個ずつ置かれています．$k$ 番目の宝はマス $(x_k, y_k)$ にあり，その $1$ 個あたりの価値は $v_k$ です．

さて，次に示す操作を，「マス $(i,j)$ に対する操作」と呼びます．

マス $(i,j)$ に対して次の条件を全て満たすマス $(x,y)$ に宝があれば，マス $(x,y)$ にある宝を $1$ つずつ獲得する．

• $x + y \geq i + j$
• $x - y \geq i - j$

あなたは，$1 \leq i \leq H, 1 \leq j \leq W$ を満たす全てのマス $(i,j)$ に対する操作を $1$ 回ずつ行いました．このとき，獲得した宝の価値の総和を $998244353$ で割った余りを求めてください．

制約

• 入力はすべて整数である．
• $1 \leq H,W \leq 50$
• $0 \leq K \leq HW$
• $1 \leq x_k \leq H$
• $1 \leq y_k \leq W$
• $0 \leq v_k \leq 10^9$
• $(x_k, y_k) \neq (x_l, y_l) (k \neq l)$

入力

入力は以下の形式で標準入力から与えられる．

$H$ $W$ $K$
$x_1$ $y_1$ $v_1$
$x_2$ $y_2$ $v_2$
$\vdots$
$x_K$ $y_K$ $v_K$

出力

獲得した宝の価値の総和を $998244353$ で割った余りを出力せよ．

サンプル

サンプル1

入力サンプルをコピー

入力

3 3 4
1 2 4
2 1 5
2 2 6
3 1 2

出力

55

マス目と，そこに置かれている宝の価値は，次の図のようになります．

例えば，マス $(1,2)$ に対する操作で，宝を獲得できる範囲を次に示します．

• マス $(1,1)$ に対する操作で獲得できる宝の価値は，$5+6+2=13$ です．
• マス $(1,2)$ に対する操作で獲得できる宝の価値は，$4+5+6+2=17$ です．
• マス $(1,3)$ に対する操作で獲得できる宝の価値は，$6+2=8$ です．
• マス $(2,1)$ に対する操作で獲得できる宝の価値は，$5+2=7$ です．
• マス $(2,2)$ に対する操作で獲得できる宝の価値は，$6+2=8$ です．
• マス $(2,3)$ に対する操作で宝は獲得できません．
• マス $(3,1)$ に対する操作で獲得できる宝の価値は，$2$ です．
• マス $(3,2)$ に対する操作で宝は獲得できません．
• マス $(3,3)$ に対する操作で宝は獲得できません．

したがって，獲得した宝の価値の総和は，$13+17+8+7+8+2=55$ となります．

サンプル2

入力サンプルをコピー

入力

3 8 4
2 2 10
2 3 10
3 2 20
3 5 30

出力

510

例えば，マス $(1,4)$ に対する操作で宝を獲得できる範囲は次の図の通りです．

2 3 2
1 2 1000000000
2 3 1000000000

7022588