Molecule Pair Distance Histogram

A research center studies how protein molecules move. To learn how the molecules gather into clusters, the center needs the distance between every pair of molecules, collected into a histogram.

Molecule positions are given as an $N \times N$ grid. The value $C_{xy}$ in cell $(x, y)$ means that $C_{xy}$ molecules sit at position $(x, y)$. Two molecules in the same cell are at distance $0$ from each other.

Given the grid, compute the average distance over all pairs of two different molecules, together with the histogram of their squared distances.

The first line contains the grid size $N$ ($1 \le N \le 1024$).

Each of the next $N$ lines contains $N$ integers. The $y$-th number on the $x$-th line is $C_{xy}$, the number of molecules at position $(x, y)$ ($0 \le C_{xy} \le 9$).

The grid holds at least $2$ molecules in total.

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

On the first line print $D_{avg}$, the average distance over all pairs of two different molecules, rounded to exactly six digits after the decimal point. Always print all six digits, so an average of $0$ prints as 0.000000. The average uses the plain Euclidean distance, not the squared distance.

Then print the histogram of squared Euclidean distances. Each line holds a squared distance $d_i$ and the number of molecule pairs $c_i$ at that distance, separated by one space. Print only the distances with $c_i > 0$, in increasing order of $d_i$.

If more than 10,000 distinct squared distances occur, print only the first 10,000 lines. The average on the first line still covers every pair.

D_avg
d1 c1
d2 c2
...
dm cm