Problem: F - Point Distance

Problem Statement

You work for invention center as a part time programmer. This center researches movement of protein molecules. It needs how molecules make clusters, so it will calculate distance of all pair molecules and will make a histogram. Molecules’ positions are given by a N x N grid map. Value C_{xy} of cell (x, y) in a grid map means that C_{xy} molecules are in the position (x, y).

You are given a grid map, please calculate histogram of all pair molecules.

Input

Input is formatted as follows.


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


First line contains the grid map size N (1 \leq N \leq 1024). Each next N line contains N numbers. Each numbers C_{xy} (0 \leq C_{xy} \leq 9) means the number of molecule in position (x,y). There are at least 2 molecules.

Output

Output is formatted as follows.


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


Print D_{ave} which an average distance of all pair molecules on first line. Next, print histogram of all pair distance. Each line contains a distance d_i and the number of pair molecules c_i(0 \lt c_i). The distance d_i should be calculated by squared Euclidean distance and sorted as increasing order. If the number of different distance is more than 10,000, please show the first 10,000 lines. The answer may be printed with an arbitrary number of decimal digits, but may not contain an absolute or relative error greater than or equal to 10^{-8}.

Sample Input 1


2
1 0
0 1


Output for the Sample Input 1


1.4142135624
2 1


Sample Input 2


3
1 1 1
1 1 1
1 1 1


Output for the Sample Input 2


1.6349751825
1 12
2 8
4 6
5 8
8 2


Sample Input 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


Output for the Sample Input 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






Example

Input

2
1 0
0 1


Output

1.4142135624
2 1

Solution (in CPP):

Solution:
#include <bits/stdc++.h>

using namespace std;

#define TemplateVersion "3.3.0"
// Useful Marcos
//====================START=====================
// Compile use C++11 and above
#ifdef LOCAL
#define debug(args...)                           \
    {                                            \
        string _s = #args;                       \
        replace(_s.begin(), _s.end(), ',', ' '); \
        stringstream _ss(_s);                    \
        istream_iterator<string> _it(_ss);       \
        err(_it, args);                          \
    }
void err(istream_iterator<string> it)
{
}
template <typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args)
{
    cerr << *it << " = " << a << endl;
    err(++it, args...);
}
#define MSG cout << "Finished" << endl
#else
#define debug(args...)
#define MSG
#endif
#if __cplusplus >= 201703L
template <typename... Args>
void readln(Args &... args)
{
    ((cin >> args), ...);
}
template <typename... Args>
void writeln(Args... args)
{
    ((cout << args << " "), ...);
    cout << endl;
}
#elif __cplusplus >= 201103L
void readln()
{
}
template <typename T, typename... Args>
void readln(T &a, Args &... args)
{
    cin >> a;
    readln(args...);
}
void writeln()
{
    cout << endl;
}
template <typename T, typename... Args>
void writeln(T a, Args... args)
{
    cout << a << " ";
    writeln(args...);
}
#endif
#if __cplusplus >= 201103L
#define FOR(_i, _begin, _end) for (auto _i = _begin; _i < _end; _i++)
#define FORR(_i, _begin, _end) for (auto _i = _begin; _i > _end; _i--)
#else
#define FOR(_i, _begin, _end) for (int _i = (int)_begin; _i < (int)_end; _i++)
#define FORR(_i, _begin, _end) for (int _i = (int)_begin; _i > (int)_end; _i--)
#define nullptr NULL
#endif
#if __cplusplus >= 201103L
#define VIS(_kind, _name, _size) \
    vector<_kind> _name(_size);  \
    for (auto &i : _name)        \
        cin >> i;
#else
#define VIS(_kind, _name, _size)    \
    vector<_kind> _name;            \
    _name.resize(_size);            \
    for (int i = 0; i < _size; i++) \
        cin >> _name[i];
#endif
// alias
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ALL(x) (x).begin(), (x).end()
// Swap max/min
template <typename T>
bool smax(T &a, const T &b)
{
    if (a > b)
        return false;
    a = b;
    return true;
}
template <typename T>
bool smin(T &a, const T &b)
{
    if (a < b)
        return false;
    a = b;
    return true;
}
// ceil divide
template <typename T>
T cd(T a, T b)
{
    return (a + b - 1) / b;
}
// min exchange
template <typename T>
bool se(T &a, T &b)
{
    if (a < b)
        return false;
    swap(a, b);
    return true;
}
// A better MAX choice
const int INF = 0x3f3f3f3f;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef set<int> si;
typedef vector<string> cb;
//====================END=====================

// Constants here
namespace FFT
{
typedef std::complex<double> Complex;
typedef std::vector<Complex> vc;

const double EPS = 0.5;

const int MaxL = 22, MaxN = 1 << MaxL;
vc eps(MaxN), inv_eps(MaxN);

void init_eps(int p)
{
    double pi = acos(-1);
    double angle = 2.0 * pi / p;
    for (int i = 0; i != p; i++)
    {
        eps[i] = Complex(cos(i * angle), sin(i * angle));
        inv_eps[i] = conj(eps[i]);
    }
}

void transform(int n, vc &x, const vc &w)
{
    for (int i = 0, j = 0; i != n; ++i)
    {
        if (i > j)
            swap(x[i], x[j]);
        for (int l = n >> 1; (j ^= l) < l; l >>= 1)
            ;
    }

    for (int i = 2; i <= n; i <<= 1)
    {
        int m = i >> 1;
        for (int j = 0; j < n; j += i)
        {
            for (int k = 0; k != m; ++k)
            {
                Complex z = x[j + m + k] * w[n / i * k];
                x[j + m + k] = x[j + k] - z;
                x[j + k] += z;
            }
        }
    }
}
} // namespace FFT

// Pre-Build Function
inline void build()
{
}

// Actual Solver
inline void solve()
{
    int n, t, x, y, val;
    ll k, sp = 0;
    int p = 1;

    map<int, ll> ans;

    scanf("%d", &n);

    int st = 2 * n * n - 1;

    while (p < st)
        p <<= 1;

    p <<= 1;

    FFT::init_eps(p);

    FFT::vc f(p), g(p);
    FOR(i, 0, n)
    {
        FOR(j, 0, n)
        {
            t = 2 * i * n + j;
            scanf("%lld", &k);
            if (k)
            {
                sp += k;
                f[t] += k * 1.0;
                g[st - t] += k * 1.0;
                if (k > 1)
                    ans[0] += k * (k - 1) / 2;
            }
        }
    }

    sp = sp * (sp - 1) / 2;

    FFT::transform(p, f, FFT::eps);
    FFT::transform(p, g, FFT::eps);

    FOR(i, 0, p)
    f[i] *= g[i];

    FFT::transform(p, f, FFT::inv_eps);

    double ave = 0.0;

    FOR(i, st + 1, p)
    {
        t = i - st;
        val = f[i].real() / p + FFT::EPS;

        if (val)
        {
            y = t % (2 * n);
            x = t / (2 * n);
            if (y >= n)
            {
                y = 2 * n - y;
                x++;
            }
            int d = x * x + y * y;
            ave += sqrt(d) * val / sp;
            ans[d] += val;
        }
    }

    printf("%.10f\n", ave);

    int cnt = 0;
    for (auto i : ans)
    {
        printf("%d %lld\n", i.first, i.second);
        cnt++;
        if (cnt >= 10000)
            break;
    }
}

int main()
{
    // ios::sync_with_stdio(false);
    // cin.tie(nullptr);
    // cout.tie(nullptr);

#ifdef LOCAL
    clock_t _begin = clock();
#endif

    build();
    solve();

#ifdef LOCAL
    cerr << "Time elapsed: " << (double)(clock() - _begin) * 1000 / CLOCKS_PER_SEC << "ms." << endl;
#endif

    return 0;
}