Мирко и Славко играются с игрушечными зверюшками. Сначала они выбирают одну с трех возможных досок для игры, как показано на рисунке. Каждая доска состоит из клеток (показаны на рисунке кружками), организованных в одно-, дву- или трехмерную решетку.
После этого Мирко размещает N зверюшек по клетках.
Расстояние между двумя клетками - это минимальное количество шагов, которые нужно сделать зверюшке, чтобы переместиться с одної клетки в другую. За один шаг зверушка может переместиться в произвольную из соседних клеток (на рисунке смежные клетки соединены отрезками). Двое зверушек могут слышать друг друга, если расстояние между их клетками не превышает число D. Задача Славка - подсчитать количество пар зверушек, которые могут слышать друг друга.
Напишите программу, которая за заданным типом доски, расположением всех зверушек на ней и числу D ищет нужное количество пар зверушек.
Первая строка входных данных содержит четыре целых числа в таком порядке: - тип доски B (1 ≤ B ≤ 3); - количество зверушек N (1 ≤ N ≤ 100 000); - максимальное расстояние D, на котором двое зверушек могут слышать друг друга (1 ≤ D ≤ 100 000 000); - размер доски M (максимальная координата, которая может встретится во входных данных): - если B = 1, то M не будет превышать 75000000; - если B = 2, то M не будет превышать 75000; - если B = 1, то M не будет превышать 75.
Каждая из последующих N строк содержит по B целых чисел, разделенных единичными пробелами - координаты соответствующей зверушки. Каждая координата находится в диапазоне от 1 до M, включительно. В одной клетке может размещаться более одной зверушки.
Выходные данные состоят из единственного целого числа - количества пар зверушек, которые могут слышать друг друга.