P7436 Draw Rectangles

The lord of Shandianbei Palace is a ninth-grade newbie and is not good at creating tricky problems. One day, they casually ACed the problem “Chinese Chess”, and suddenly got an idea...

The lord of Shandianbei Palace drew an $n \times m$ rectangular grid. Specifically, it contains all integer points with coordinates $(x,y)$ ($x\in [0,n], y\in [0,m]$), and all edges connecting pairs of points with distance $1$. Now they want to know how many rectangles with perimeter not greater than $k$ can be drawn inside this grid (all four sides of the rectangle must be parallel to the coordinate axes). But even as an easy warm-up problem, this would still be too simple, so they added $q$ obstacle points and require that the chosen rectangle **does not contain** any obstacle point. Each obstacle point is a $1\times 1$ square. Now the lord of Shandianbei Palace is going to make other “easy (tricky)” problems, can you help solve this one? Output the answer modulo $998244353$.

The first line contains four positive integers $n$, $m$, $q$, and $k$. The next $q$ lines each contain two numbers, the $x$ coordinate and the $y$ coordinate of an obstacle (an obstacle at coordinate $(x,y)$ has four vertices $(x-1,y-1),(x-1,y),(x,y-1),(x,y)$).

Output one line with one integer, the number of rectangles modulo $998244353$.

#### Sample Explanation Sample #1: All cells except the $4$ obstacle cells are valid rectangles. Therefore, the answer is $3\times 3-4=5$. Sample #2: This is just counting the number of valid rectangles. There are $5$ rectangles of size $1\times 1$, and $3$ rectangles in total of sizes $1\times 2$ and $2\times 1$, so the answer is $5+3=8$. #### Constraints | ID | $n,m$ | $k$ | $q$ | | :----------: | :----------: | :----------: | :----------: | | $1,2$ | $\le 10^3$ | $\le 1.5\times 10^9$ | $=0$ | | $3,4,5,6$ | $\le 1.5\times 10^9$ | $\le 1.5\times 10^9$ | $=0$ | | $7,8$ | $\le 20$ | $\le 1.5\times 10^9$ | $\le 20$ | | $9,10$ | $\le 1.5\times 10^9$ | $\le 20$ | $\le 20$ | | $11,12,13,14$ | $\le 1.5\times 10^9$ | $\le 10^5$ | $\le 20$ | | $15,16,17,18,19,20$ | $\le 1.5\times 10^9$ | $\le 1.5\times 10^9$ | $\le 20$ | For $100\%$ of the testdata, $1\le n,m \le 1.5\times 10^9$, $4\le k \le 1.5\times 10^9$, $0\le q \le 20$. It is guaranteed that all obstacles are valid and pairwise distinct. Translated by ChatGPT 5