Description

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$.

Input Format

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 Format

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

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

5

3 3 4 10000
1 1
2 2
3 3
2 3

8

Hint

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

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