장난감 동물

상근이와 선영이는 장난감 동물을 가지고 논다. 먼저 아래 세 종류의 게임판 중 하나를 고른다. 각 게임판은 여러 개의 칸으로 이루어져 있으며, $1$번 게임판은 1차원(직선), $2$번은 2차원(격자), $3$번은 3차원(입체 격자) 모양이다.

각 칸은 정수 좌표로 나타내고, 서로 인접한 칸은 선분으로 연결되어 있다.

• $1$번 게임판: 칸을 좌표 $x$로 나타내며, 칸 $x$는 칸 $x-1$, $x+1$과 인접하다.
• $2$번 게임판: 칸을 좌표 $(x, y)$로 나타내며, 칸 $(x, y)$는 $(x\pm1,\ y)$, $(x,\ y\pm1)$과 인접하다.
• $3$번 게임판: 칸을 좌표 $(x, y, z)$로 나타내며, 칸 $(x, y, z)$는 $(x\pm1,\ y,\ z)$, $(x,\ y\pm1,\ z)$, $(x,\ y,\ z\pm1)$과 인접하다.

상근이는 $N$마리의 장난감 동물을 칸에 놓는다. 한 칸에 여러 마리가 놓일 수도 있다.

두 칸 사이의 거리는 한 칸에서 다른 칸까지 가는 데 필요한 최소 이동 횟수이다. 한 번 이동할 때마다 인접한 칸으로 갈 수 있으므로, 두 칸의 거리는 좌표별 차이의 절댓값을 모두 더한 값과 같다.

• $1$번 게임판: $|x_1 - x_2|$
• $2$번 게임판: $|x_1 - x_2| + |y_1 - y_2|$
• $3$번 게임판: $|x_1 - x_2| + |y_1 - y_2| + |z_1 - z_2|$

두 장난감 동물은 둘이 놓인 칸 사이의 거리가 $D$ 이하일 때 서로의 소리를 들을 수 있다. 게임판의 종류, 각 장난감 동물의 위치, 그리고 $D$가 주어졌을 때, 서로의 소리를 들을 수 있는 장난감 동물 쌍의 개수를 구하는 프로그램을 작성하시오.

첫째 줄에 네 정수 $B$, $N$, $D$, $M$이 공백으로 구분되어 주어진다.

• $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 \le 75,000,000$, $B = 2$이면 $M \le 75,000$, $B = 3$이면 $M \le 75$이다.

다음 $N$개의 줄에 각 장난감 동물의 좌표가 주어진다. $B$번 게임판에서는 한 줄에 정수 $B$개가 공백으로 구분되어 주어진다. 즉 $B = 1$이면 $x$, $B = 2$이면 $x\ y$, $B = 3$이면 $x\ y\ z$가 주어지며, 모든 좌표는 $1$ 이상 $M$ 이하의 자연수이다. 같은 칸에 여러 마리가 놓일 수도 있다.

서로의 소리를 들을 수 있는 장난감 동물 쌍의 개수를 첫째 줄에 출력한다.