#2053. SRM199 ClosestPoints

内存限制:64 MiB 时间限制:10 Sec

题目描述

给出N,Range,Seed_0,按照Seed_{i+1} = (Seed_i * 16807) mod (2^31-1)以及Rand_i = (Seed_i mod (2 * Range)) – Range的规则,计算出Rand_1 到Rand_{3n} 。定义三维空间内的点P_k的坐标为(Rand_{3k-2}, Rand_{3k-1}, Rand_{3k}){1≤k≤n}。求出所有点中两点间最小距离的平方以及有多少对点的距离等于最小距离。 2 ≤ N ≤ 150000,1 ≤ Range ≤ 10^6,1 ≤ Seed ≤ 10^3 
注意:如果有多个点重合,就当成一个点

输入格式

输出格式

样例

样例输入


			
3
100
1

样例输出


			
9163
1

数据范围与提示

The three points are: (-93, -51, -27), (-42, 30, -28), and (44, -22, 23). The closest pair of points are the first and third, and the square of their distance is 9163. There is 1 pair of points with a squared distance of 9163.