[SDCPC2023] Be Careful 2

**【题目描述】** 小青鱼有一个位于二维平面上的，大小为 $n \times m$ 的矩形。矩形的右上角位于 $(n, m)$，而左下角位于 $(0, 0)$。矩形内部有 $k$ 个禁止点，第 $i$ 个禁止点位于 $(x_i, y_i)$。 小青鱼想在矩形里画一个正方形。但由于小青鱼不喜欢禁止点，因此正方形的内部不能有任何禁止点。更正式地，小青鱼可以画一个左下角位于 $(x, y)$ 且边长为 $d$ 的正方形，当且仅当： - $x$ 和 $y$ 都是非负整数，$d$ 是一个正整数。 - $0 \leq x < x+d \leq n$。 - $0 \leq y < y+d \leq m$。 - 每个 $1 \leq i \leq k$ 都 **不能** 满足以下条件： - $x < x_i < x+d$ 且 $y < y_i < y+d$。 请计算小青鱼可以画的正方形的总面积。由于答案可能很大，请将答案对 $998244353$ 取模后输出。 **【输入格式】** 每个测试文件仅有一组测试数据。 第一行输入三个整数 $n$，$m$ 和 $k$（$2 \leq n,m \leq 10^9$，$1 \leq k \leq 5 \times 10^3$），表示矩形的大小和禁止点的数量。 对于接下来 $k$ 行，第 $i$ 行输入两个整数 $x_i$ 和 $y_i$（$0 < x_i < n$，$0 < y_i < m$）表示第 $i$ 个禁止点的位置。保证所有禁止点互不相同。 **【输出格式】** 输出一行一个整数，代表对 $998244353$ 取模后的答案。 **【样例解释】** 对于第一组样例数据，小青鱼有 $12$ 种方式画一个正方形，如下图所示。  共有 $9$ 个边长为 $1$ 的正方形和 $3$ 个边长为 $2$ 的正方形。因此答案为 $9 \times 1^2 + 3 \times 2^2 = 21$。 以下画正方形的方式是不合法的，因为正方形内有一个禁止点。 

# 警告：滥用本题评测将被封禁。

Little Cyan Fish has an $n \times m$ rectangle located in a plane. The top-right corner of the rectangle is at $(n, m)$, while the bottom-left corner is at $(0, 0)$. There are $k$ banned points inside the rectangle. The $i$-th banned point is located at $(x_i, y_i)$. Little Cyan Fish would like to draw a square inside the rectangle. However, he dislikes all the banned points, so there cannot be any banned points inside his square. Formally, Little Cyan Fish can draw a square with the bottom-left corner at $(x, y)$ and a side length $d$ if and only if: - Both $x$ and $y$ are non-negative integers while $d$ is a positive integer. - $0 \leq x < x+d \leq n$. - $0 \leq y < y+d \leq m$. - For each $1 \leq i \leq k$, the following condition must **NOT** be met: - $x < x_i < x+d$ and $y < y_i < y+d$. Please calculate the sum of the areas of all the squares that Little Cyan Fish can possibly draw. Since the answer could be huge, you need to output it modulo $998244353$.

The is only one test case in each test file. The first line of the input contains three integers $n$, $m$ and $k$ ($2 \leq n,m \leq 10^9$, $1 \leq k \leq 5 \times 10^3$) indicating the size of the rectangle and the number of banned points. For the following $k$ lines, the $i$-th line contains two integers $x_i$ and $y_i$ ($0 < x_i < n$, $0 < y_i < m$) indicating the position of the $i$-th banned point. It is guaranteed that all the banned points are distinct.

Output one line containing one integer indicating the answer modulo $998244353$.

3 3 1
2 2

21

5 5 2
2 1
2 4

126

For the first sample test case, Little Cyan Fish has $12$ ways to draw a square, illustrated as follows.  There are $9$ squares of side length $1$ and $3$ squares of side length $2$. So the answer is $9 \times 1^2 + 3 \times 2^2 = 21$. Note that the following plans are invalid since there's a banned point in the square.