Problem A
Beslutsångest

Nikolaj bor i en stad som består av ett $N \times M$-rutnät, där raderna är numrerade från $1$ till $N$ och kolumnerna är numrerade från $1$ till $M$. En cell i rutnätet på rad nummer $r$ och kolumn nummer $c$ brukar betecknas $(r, c)$. Eftersom Nikolaj inte har något jobb har han varit på en massa intervjuer och fått erbjudanden av $K$ stycken företag. Det $i$:te företaget har sitt kontor i cellen $(r_ i, c_ i)$, och inga två företag har kontor på samma cell. Det enda som återstår för Nikolaj är att gå till en av dessa celler, så blir han direkt anställd på företaget som har sitt kontor där. För att bestämma vilken cell han ska gå till har Nikolaj mätt varje jobbs nyttighet, som är ett heltal mellan $-10^9$ och $10^9$. Ett jobbs nyttighet är ett mått på hur mycket nytta Nikolaj skulle göra om han började där. Att sitta hemma och göra ingenting har t.ex. nyttan $0$.

Nu kanske det låter som att Nikolajs val borde vara enkelt, men tyvärr är det långt ifrån sant. Nikolaj tycker nämligen att ju mindre nyttigt ett jobb är, desto roligare är det. Han kan därför inte bestämma sig för om han borde maximera eller minimera nyttigheten. Nikolaj kommer starta vid någon cell $(r, c)$, och från början är han inställd på att minimera nyttigheten. Varje sekund kommer han gå till antingen cell $(r+1, c)$ eller $(r, c+1)$, och efter att ha gått ett steg ändrar han sig och vill istället maximera nyttigheten. Därefter upprepas processen så att han omväxlande vill minimera, maximera, minimera, maximera osv. Detta upprepas tills dess att Nikolaj hamnar på ett av företagens kontor, eller hamnar utanför rutnätet. Om Nikolaj missar alla kontor och hamnar utanför rutnätet får han inget jobb och uppnår därmed nyttighet $0$.

När Nikolaj väljer vilken cell han ska gå till gör han det alltid optimalt så att nyttan minimeras/maximeras, och han är medveten om sin “andra personlighet” och hur den beter sig. Om du vill kan du tänka dig situationen som ett spel där Nikolajs två personligheter spelar mot varandra. Om Nikolaj startar vid en cell som är ett kontor blir han direkt anställd där innan han hinner gå någonstans.

Nikolaj har grubblat mycket på hur startpunkten $(r, c)$ påverkar vilket jobb han till slut får. Låt oss säga att nyttigheten Nikloaj uppnår om han startar vid $(r, c)$ är $N(r, c)$. Din uppgift är att räkna ut summan av $N(r, c)$ över alla de $NM$ cellerna i rutnätet. Eftersom talet kan bli ganska stort ska du skriva ut det modulo $998244353$.

Indata

Den första raden innehåller tre heltal $N$, $M$ och $K$ ($1 \leq N,M \leq 10^9$, $1 \leq K \leq \min (NM, 10^5)$).

De följande $K$ raderna innehåller tre heltal $r_ i$, $c_ i$ och $v_ i$, vilket betyder att det $i$:te företaget har sitt kontor på cellen $(r_ i, c_ i)$ och har nyttighet $v_ i$ ($1 \leq r_ i \leq N$, $1 \leq c_ i \leq M$, $-10^9 \leq v_ i \leq 10^9$).

Utdata

Skriv ut ett heltal, summan av den slutgiltiga nyttigheten över alla de $NM$ cellerna, modulo $998244353$.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

3 3 3
2 3 -2
3 1 3
1 2 1

998244352

2 4 3
1 2 2
2 4 -3
2 1 1

998244348