尘埃下的神话

题目信息

时间限制: 1s

空间限制: 512M

输入文件: history.in

输出文件: history.out

题目描述

华夏大陆在战国时代分裂成了 $m$ 个诸侯国，考古学家们将它们从 $1\sim m$ 编号。华夏的考古学家们在今年发现了 $n$ 处战国时代遗址，将华夏大陆看作二维平面，第 $i$ 处遗址的坐标为 $\left(x_i, y_i\right)$。

每处遗址只会属于 $m$ 个诸侯国中的某一个。也可能存在若干个诸侯国，在无情的岁月长河里它们曾有的历史没有留下任何痕迹（即今年发现的遗址不属于这些诸侯国）。限于战国时代的生产力水平，对于每个诸侯国，必定存在一个边长为 $K$ 且四边平行于坐标轴的正方形，它能覆盖这个诸侯国留下的所有遗址（正方形边界上的遗址也看作被覆盖）。

那么共有多少种诸侯国和遗址的对应方式呢？求答案对 998244353 取模的结果。

输入格式

第一行，三个正整数，依次表示 $m, n, K$，含义如题所示。

接下来 $n$ 行，每行一个遗址的坐标 $x_i, y_i$。

输出格式

一行一个非负整数，表示答案。

样例

样例输入 1

3 6 3
1 2
2 1
3 4
4 3
5 6
6 5

样例输出 1

162

样例解释 1

当且仅当以下情况方案合法：

• 1,5 号遗址属于不同诸侯国。
• 1,6 号遗址属于不同诸侯国。
• 2,5 号遗址属于不同诸侯国。
• 2,6 号遗址属于不同诸侯国。

对应方案共用 162 种。

数据范围与提示

对于所有数据，$1 \leq x_i, y_i, K \leq 2 \times 10^8$，且不存在两个遗址位于相同位置。