분자 쌍 거리 히스토그램

어느 연구소에서 단백질 분자의 움직임을 연구한다. 분자가 어떻게 뭉치는지 알아내려면 모든 분자 쌍의 거리를 구해 히스토그램으로 정리해야 한다.

분자의 위치는 $N \times N$ 격자로 주어진다. 칸 $(x, y)$에 적힌 값 $C_{xy}$는 위치 $(x, y)$에 분자가 $C_{xy}$개 있다는 뜻이다. 같은 칸에 있는 두 분자 사이의 거리는 $0$이다.

격자가 주어지면 서로 다른 두 분자로 이루어진 모든 쌍의 평균 거리와 제곱 거리 히스토그램을 구하라.

첫 줄에 격자의 크기 $N$이 주어진다 ($1 \le N \le 1024$).

이어지는 $N$개의 줄에는 각각 정수 $N$개가 주어진다. $x$번째 줄의 $y$번째 수 $C_{xy}$는 위치 $(x, y)$에 있는 분자의 개수다 ($0 \le C_{xy} \le 9$).

격자 전체의 분자는 $2$개 이상이다.

N
C11 C12 ... C1N
C21 C22 ... C2N
...
CN1 CN2 ... CNN

첫 줄에 서로 다른 두 분자로 이루어진 모든 쌍의 평균 거리 $D_{avg}$를 소수점 아래 여섯째 자리까지 반올림해 출력한다. 여섯 자리를 항상 모두 적으므로 평균이 $0$이면 0.000000으로 출력한다. 평균은 제곱하지 않은 유클리드 거리로 계산한다.

그 다음 줄부터 제곱 유클리드 거리 히스토그램을 출력한다. 각 줄에 제곱 거리 $d_i$와 그 거리에 해당하는 분자 쌍의 개수 $c_i$를 공백 하나로 구분해 출력한다. $c_i > 0$인 거리만 $d_i$의 오름차순으로 출력한다.

서로 다른 제곱 거리가 10,000개를 넘으면 앞의 10,000줄만 출력한다. 첫 줄의 평균 거리는 이때도 모든 쌍을 대상으로 계산한다.

D_avg
d1 c1
d2 c2
...
dm cm