题目描述

你在一个发明中心兼职程序员。这个中心研究蛋白质分子的运动方式。它需要了解分子如何聚集在一起，因此需要计算所有成对分子之间的距离，并制作直方图。分子的位置由一个 $N \times N$ 的网格地图给出。网格地图中单元格 $(x, y)$ 的值 $C_{xy}$ 表示位置 $(x, y)$ 上有 $C_{xy}$ 个分子。

给定一个网格地图，请计算所有成对分子的直方图。

输入

输入数据的格式如下。

$N$ $C_{11}$ $C_{12}$ ... $C_{1N}$ $C_{21}$ $C_{22}$ ... $C_{2N}$ ... $C_{N1}$ $C_{N2}$ ... $C_{NN}$

第一行包含网格地图的大小 $N$（$1 \leq N \leq 1024$）。接下来的 $N$ 行，每行包含 $N$ 个数。每个数 $C_{xy}$（$0 \leq C_{xy} \leq 9$）表示位置 $(x,y)$ 上的分子数量。至少有 2 个分子。

输出

输出数据的格式如下。

$D_{ave}$ $d_{1}$ $c_{1}$ $d_{2}$ $c_{2}$ ... $d_{m}$ $c_{m}$

第一行打印平均分子间距离 $D_{ave}$。接下来，打印所有成对分子之间距离的直方图。每行包含一个距离 $d_i$ 和成对分子数量 $c_i(0 < c_i)$。距离 $d_i$ 应按升序计算并排序。如果不同距离的数量超过 10,000，则只显示前 10,000 行。答案可以包含任意小数位数的十进制数字，但不能包含大于或等于 $10^{-8}$ 的绝对或相对误差。

示例输入1

2
1 0
0 1

示例输出1

1.4142135624
2 1

示例输入2

3
1 1 1
1 1 1
1 1 1

示例输出2

1.6349751825
1 12
2 8
4 6
5 8
8 2

示例输入3

5
0 1 2 3 4
5 6 7 8 9
1 2 3 2 1
0 0 0 0 0
0 0 0 0 1

示例输出3

1.8589994382
0 125
1 379
2 232
4 186
5 200
8 27
9 111
10 98
13 21
16 50
17 37
18 6
20 7
25 6

来源

日本校友团春季竞赛2013