결정 장애

Nikolaj는 $N \times M$ 크기의 격자로 이루어진 도시에 산다. 행은 1부터 $N$까지, 열은 1부터 $M$까지 번호가 매겨져 있다. 행 $r$, 열 $c$에 있는 칸은 $(r, c)$로 적는다. Nikolaj는 일자리가 없어서 $K$개 회사에서 제안을 받았다. $i$번째 회사의 사무실은 칸 $(r_i, c_i)$에 있으며, 같은 칸에 사무실이 두 개 있는 경우는 없다. Nikolaj는 이 칸 중 하나에 들어가기만 하면, 그 칸에 사무실이 있는 회사에 바로 채용된다. 어느 칸으로 갈지 정하기 위해 각 일자리의 효용을 잰다. 효용은 $-10^9$ 이상 $10^9$ 이하의 정수이며, 그 일을 하면 Nikolaj에게 얼마나 이로운지를 나타낸다. 집에서 아무것도 하지 않는 경우의 효용은 $0$이다.

Nikolaj는 $(r, c)$ 칸에서 출발하며, 처음에는 효용을 최소화하려고 한다. 매초 $(r+1, c)$ 또는 $(r, c+1)$ 중 한 칸으로 이동한다. 한 칸 이동할 때마다 마음이 바뀌어 이번에는 효용을 최대화하려고 한다. 이렇게 최소화와 최대화가 번갈아 반복된다. 과정은 Nikolaj가 사무실 칸에 도달하거나 격자 밖으로 벗어날 때까지 계속된다. 모든 사무실을 지나쳐 격자 밖으로 나가면 일자리를 얻지 못하고 효용은 $0$이 된다.

Nikolaj는 이동할 때마다 현재 목표에 가장 맞는 칸을 고르며, 다른 성격이 어떻게 행동할지도 알고 있다. 두 성격이 서로 겨루는 게임으로 생각해도 된다. 출발 칸이 사무실이면 곧바로 그곳에 채용된다.

$N(r, c)$를 Nikolaj가 $(r, c)$에서 출발했을 때 얻는 효용이라 하자. $NM$개 칸 전체에 대해 $N(r, c)$의 합을 구하라. 결과는 $998244353$으로 나눈 나머지를 출력한다.

첫 줄에 정수 $N$, $M$, $K$가 주어진다 ($1 \leq N,M \leq 10^9$, $1 \leq K \leq \min(NM, 10^5)$).

이어지는 $K$개 줄에는 정수 $r_i$, $c_i$, $v_i$가 주어진다. 이는 $i$번째 회사의 사무실이 칸 $(r_i, c_i)$에 있고, 그 일자리의 효용이 $v_i$라는 뜻이다 ($1 \leq r_i \leq N$, $1 \leq c_i \leq M$, $-10^9 \leq v_i \leq 10^9$).

$NM$개 칸 모두에 대해 최종 효용의 합을 구하고, $998244353$으로 나눈 나머지를 정수 하나로 출력한다.