{"problem":{"name":"[SDCPC 2023] Be Careful 2","description":{"content":"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","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":7000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9563"},"statements":[{"statement_type":"Markdown","content":"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)$.\n\nLittle 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:\n\n- Both $x$ and $y$ are non-negative integers while $d$ is a positive integer.\n- $0 \\leq x < x+d \\leq n$.\n- $0 \\leq y < y+d \\leq m$.\n- For each $1 \\leq i \\leq k$, the following condition must **NOT** be met:\n  - $x < x_i < x+d$ and $y < y_i < y+d$.\n\nPlease 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$.\n\n## Input\n\nThe is only one test case in each test file.\n\nThe 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.\n\nFor 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.\n\n## Output\n\nOutput one line containing one integer indicating the answer modulo $998244353$.\n\n[samples]\n\n## Note\n\nFor the first sample test case, Little Cyan Fish has $12$ ways to draw a square, illustrated as follows.\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/7ineydu5.png)\n\nThere 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$.\n\nNote that the following plans are invalid since there's a banned point in the square.\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/qgn1qs0h.png)","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9563","tags":["2023","山东","O2优化","容斥原理","省赛/邀请赛"],"sample_group":[["3 3 1\n2 2\n","21\n"],["5 5 2\n2 1\n2 4\n","126\n"]],"created_at":"2026-03-03 11:09:25"}}