SRM199 ClosestPoints

给定整数 $N$、$\mathrm{Range}$ 和初始种子 $\mathrm{Seed}_0$。按照以下递推关系生成随机数序列：

$$\mathrm{Seed}_{i+1}=(\mathrm{Seed}_i\times 16807)\bmod(2^{31}-1),$$ $$\mathrm{Rand}_i=(\mathrm{Seed}_i\bmod(2\times\mathrm{Range}))-\mathrm{Range}.$$

计算 $\mathrm{Rand}_1$ 至 $\mathrm{Rand}_{3N}$，并定义三维空间中的点 $P_k$ 为：

$$P_k=(\mathrm{Rand}_{3k-2},\mathrm{Rand}_{3k-1},\mathrm{Rand}_{3k}),\qquad 1\le k\le N.$$

求所有不同点对之间距离平方的最小值，以及距离平方等于该最小值的点对数量。

如果有多个点重合，则将它们视为同一个点。

输入格式

输入共 $3$ 行。

第 $1$ 行包含一个整数 $N$。

第 $2$ 行包含一个整数 $\mathrm{Range}$。

第 $3$ 行包含一个整数 $\mathrm{Seed}_0$。

输出格式

输出共 $2$ 行。

第 $1$ 行输出两点间最小距离的平方。

第 $2$ 行输出距离平方等于该最小值的点对数量。

样例输入

3
100
1

样例输出

9163
1

样例解释

生成的 $3$ 个点分别为 $(-93,-51,-27)$、$(-42,30,-28)$ 和 $(44,-22,23)$。

其中，第 $1$ 个点与第 $2$ 个点的距离平方最小，为 $9163$。距离平方等于 $9163$ 的点对共有 $1$ 对。

数据范围

• $2\le N\le 150000$；
• $1\le\mathrm{Range}\le 10^6$；
• $1\le\mathrm{Seed}_0\le 10^3$。

来源与许可

本题为 Topcoder SRM 199 试题「ClosestPoints」，题面与测试数据整理自 BZOJ 2053。

样例 1

输入

3
100
1

输出

9163
1