题目背景

扇贝宫主是一个初三的菜鸡，不擅长出毒瘤题。这天，Ta随手 A 了中国象棋这题，忽然灵光乍现...

题目描述

扇贝宫主画了一个 $n \times m$ 的矩形网格图。具体来说，包含坐标 $(x,y)$（$x\in [0,n], y\in [0,m]$）的所有整点以及所有连接距离为 $1$ 的点的边。

这时，扇贝宫主突发奇想，想知道这个矩形里面能够绘制多少个周长不大于 $k$ 的矩形（矩形的四边必须平行于坐标轴）。但这即使作为签到题也未免太简单了些，于是扇贝宫主加入了 $q$ 个障碍点，要求选取的矩形不包含障碍点。每个障碍点都是一个 $1\times 1$ 的正方形。现在扇贝宫主要继续出其他签（毒）到（瘤）题了，你能帮忙解决此题吗？答案对 $998244353$ 取模。

输入格式

第 $1$ 行包含四个正整数 $n$，$m$，$q$ 和 $k$。

接下来 $q$ 行，第 $i$ 行包含 $2$ 个数，分别为障碍物的 $x$ 坐标与 $y$ 坐标（一个坐标为 $(x,y)$ 的障碍点四个顶点为 $(x-1,y-1),(x-1,y),(x,y-1),(x,y)$）。

输出格式

输出共一行一个整数，即矩形个数对 $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

提示

【样例解释】

样例 #1：除了 $4$ 个障碍物格子之外剩下的格子都是合法的矩形。因此答案为 $3\times 3-4=5$。

样例 #2：即统计合法的矩形个数。$1\times 1$ 的矩形有 $5$ 个，$1\times 2$ 和 $2\times 1$ 的矩形共 $3$ 个，因此答案为 $5+3=8$。

【数据范围】

对于 $100\%$ 的数据，$1\le n,m \le 1.5\times 10^9$，$4\le k \le 1.5\times 10^9$，$0\le q \le 20$。保证输入的障碍物合法且两两不同。