题目描述

Bob 在平面中绘制了 $N$ 个黑点和 $N$ 个白点，并在每一对点之间绘制有向边。对于每一对点 $p$ 和 $q$，Bob 按照下述规则绘制边。

• 若两点颜色相同，则可选择绘制边 $p \to q$ 或 $q \to p$。
• 若两点颜色不同，不妨设 $p$ 为白点、$q$ 为黑点：如果 $\text{dist}(p, q) > D$ 则绘制边 $p \to q$，否则绘制边 $q \to p$。

距离函数定义为 $\text{dist}(p, q) = |p.x - q.x| + |p.y - q.y|$。

Bob 认为，一个由点 $p$、$q$ 和 $r$ 组成的 美丽三角形（即一个三点组）应满足以下条件：

• 其中至少有一个黑点，至少有一个白点。
• $p \to q$、$q \to r$、$r \to p$ 是它们之间的全部边。

现在 Bob 想知道可能存在的美丽三角形的最小数量和最大数量。

输入格式

输入包含多组测试数据，请处理到文件末尾。

对于每组测试数据，第一行包含两个整数 $N$ ($N \le 100000$) 和 $D$。接下来的 $N$ 行，每行包含两个整数，表示一个白点的坐标。再接下来的 $N$ 行，每行包含两个整数，表示一个黑点的坐标。一些点可能坐标相同。

输入中的所有数字均为非负整数且小于 $2^{31}$。

输出格式

对于每组测试数据，输出两个整数，分别表示美丽三角形的最小可能数量和最大可能数量。

2 1
1 2
1 1
3 1
2 2

0 2

提示

翻译由 DeepSeek V4 Pro 完成