Mirko 和 Slavko 正在玩玩具动物。首先，他们从下图中选择一块棋盘。每块棋盘由若干单元格（图中以圆圈表示）组成，这些单元格排列成一维、二维或三维网格。

Board 1, Board 2, Board 3

随后，Mirko 将 $N$ 只小玩具动物放置在这些单元格中。

两个单元格之间的距离是指一只动物从一个单元格到达另一个单元格所需的最少移动步数。在一次移动中，动物可以步入相邻的单元格（图中由线段连接的单元格）。

如果两只动物所在单元格之间的距离最多为 $D$，则它们可以互相听到。Slavko 的任务是计算有多少对动物满足其中一只可以听到另一只。

任务

编写一个程序，给定棋盘类型、所有动物的位置以及距离 $D$，求出满足条件的动物对数。

输入格式

输入的第一行包含四个整数，顺序如下： 棋盘类型 $B$ ($1 \le B \le 3$)； 动物数量 $N$ ($1 \le N \le 100\,000$)； 两只动物能互相听到的最大距离 $D$ ($1 \le D \le 100\,000\,000$)； 棋盘大小 $M$（输入中允许出现的最大坐标）： 当 $B=1$ 时，$M$ 最大为 $75\,000\,000$。 当 $B=2$ 时，$M$ 最大为 $75\,000$。 * 当 $B=3$ 时，$M$ 最大为 $75$。

接下来的 $N$ 行，每行包含 $B$ 个由空格分隔的整数，表示一只玩具动物的坐标。每个坐标都在 $1$ 到 $M$ 之间（含 $1$ 和 $M$）。

同一单元格内可能有多只动物。

输出格式

输出应为一个整数，即能够互相听到的动物对数。

说明：请使用 64 位整数类型来计算并输出结果（C/C++ 中的 long long，Pascal 中的 int64）。

子任务

在总分 30 分的测试用例中，动物数量 $N$ 最多为 $1\,000$。 此外，对于三种棋盘类型中的每一种，能够正确解决该类型所有测试用例的方案将至少获得 30 分。

样例

输入 1

1 6 5 100 
25 
50 
50 
10 
20 
23

输出 1

4

说明 1

最左侧样例的说明。假设动物按给出的顺序编号为 1 到 6。这四对分别是： 1-5（距离 5） 1-6（距离 2） 2-3（距离 0） 5-6（距离 3）

输入 2

2 5 4 10 
5 2 
7 2 
8 4 
6 5 
4 4

输出 2

8

说明 2

中间样例的说明。这八对分别是： 1-2（距离 2） 1-4（距离 4） 1-5（距离 3） 2-3（距离 3） 2-4（距离 4） 3-4（距离 3） 3-5（距离 4） 4-5（距离 3）

输入 3

3 8 10 20 
10 10 10 
10 10 20 
10 20 10 
10 20 20 
20 10 10 
20 10 20 
20 20 10 
20 20 20

输出 3

12