Problem: The Smart Beaver from ABBYY loves puzzles. One of his favorite puzzles is the magic square. He has recently had an idea to automate the solution of this puzzle. The Beaver decided to offer this challenge to the ABBYY Cup contestants.

The magic square is a matrix of size n × n. The elements of this matrix are integers. The sum of numbers in each row of the matrix is equal to some number s. The sum of numbers in each column of the matrix is also equal to s. In addition, the sum of the elements on the main diagonal is equal to s and the sum of elements on the secondary diagonal is equal to s. Examples of magic squares are given in the following figure:

<image> Magic squares 

You are given a set of n2 integers ai. It is required to place these numbers into a square matrix of size n × n so that they form a magic square. Note that each number must occur in the matrix exactly the same number of times as it occurs in the original set.

It is guaranteed that a solution exists!

Input

The first input line contains a single integer n. The next line contains n2 integers ai ( - 108 ≤ ai ≤ 108), separated by single spaces.

The input limitations for getting 20 points are: 

  * 1 ≤ n ≤ 3



The input limitations for getting 50 points are: 

  * 1 ≤ n ≤ 4
  * It is guaranteed that there are no more than 9 distinct numbers among ai. 



The input limitations for getting 100 points are: 

  * 1 ≤ n ≤ 4

Output

The first line of the output should contain a single integer s. In each of the following n lines print n integers, separated by spaces and describing the resulting magic square. In the resulting magic square the sums in the rows, columns and diagonals must be equal to s. If there are multiple solutions, you are allowed to print any of them.

Examples

Input

3
1 2 3 4 5 6 7 8 9


Output

15
2 7 6
9 5 1
4 3 8


Input

3
1 0 -1 0 2 -1 -2 0 1


Output

0
1 0 -1
-2 0 2
1 0 -1


Input

2
5 5 5 5


Output

10
5 5
5 5

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 4;
int n;
int a[MAX_N * MAX_N];
bool used[MAX_N * MAX_N];
bool check(int x[4][4], int n) {
  int sum = 0;
  for (int i = 0; i < n; ++i) {
    sum += x[0][i];
  }
  for (int r = 0; r < n; ++r) {
    if (accumulate(x[r], x[r] + n, 0) != sum) {
      return false;
    }
  }
  for (int c = 0; c < n; ++c) {
    int t = 0;
    for (int r = 0; r < n; ++r) {
      t += x[r][c];
    }
    if (t != sum) return false;
  }
  int A = 0, B = 0;
  for (int r = 0; r < n; ++r) {
    A += x[r][r];
    B += x[r][n - 1 - r];
  }
  if (A != sum || B != sum) return false;
  return true;
}
void work3() {
  sort(a, a + n * n);
  do {
    int x[4][4];
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        x[i][j] = a[i * n + j];
      }
    }
    int sum = 0;
    for (int i = 0; i < n; ++i) {
      sum += x[0][i];
    }
    bool ok = true;
    for (int r = 0; r < n; ++r) {
      if (accumulate(x[r], x[r] + n, 0) != sum) {
        ok = false;
        break;
      }
    }
    for (int c = 0; c < n; ++c) {
      int t = 0;
      for (int r = 0; r < n; ++r) {
        t += x[r][c];
      }
      if (t != sum) ok = false;
    }
    int A = 0, B = 0;
    for (int r = 0; r < n; ++r) {
      A += x[r][r];
      B += x[r][n - 1 - r];
    }
    if (A != sum || B != sum) ok = false;
    if (ok) {
      cout << sum << endl;
      for (int r = 0; r < n; ++r) {
        for (int c = 0; c < n; ++c) {
          cout << x[r][c] << " ";
        }
        cout << endl;
      }
      cout << endl;
      return;
    }
  } while (next_permutation(a, a + n * n));
}
int main() {
  cin >> n;
  for (int i = 0; i < n * n; ++i) {
    cin >> a[i];
  }
  if (n <= 3) {
    work3();
    return 0;
  }
  int sum = 0;
  for (int i = 0; i < n * n; ++i) {
    sum += a[i];
  }
  sum /= n;
  bool used[MAX_N * MAX_N] = {};
  int tot = n * n;
  for (int a11 = 0; a11 < tot; a11++)
    if (!used[a11]) {
      used[a11] = true;
      for (int a22 = 0; a22 < tot; a22++)
        if (!used[a22]) {
          used[a22] = true;
          for (int a33 = 0; a33 < tot; a33++)
            if (!used[a33]) {
              used[a33] = true;
              int need44 = sum - (a[a11] + a[a22] + a[a33]);
              for (int a44 = 0; a44 < tot; a44++)
                if (!used[a44])
                  if (a[a44] == need44) {
                    used[a44] = true;
                    for (int a14 = 0; a14 < tot; a14++)
                      if (!used[a14]) {
                        used[a14] = true;
                        for (int a23 = 0; a23 < tot; a23++)
                          if (!used[a23]) {
                            used[a23] = true;
                            for (int a32 = 0; a32 < tot; a32++)
                              if (!used[a32]) {
                                used[a32] = true;
                                int need41 = sum - (a[a14] + a[a23] + a[a32]);
                                for (int a41 = 0; a41 < tot; a41++)
                                  if (!used[a41])
                                    if (a[a41] == need41) {
                                      used[a41] = true;
                                      for (int a12 = 0; a12 < tot; a12++)
                                        if (!used[a12]) {
                                          used[a12] = true;
                                          int need42 =
                                              sum - (a[a12] + a[a22] + a[a32]);
                                          for (int a42 = 0; a42 < tot; a42++)
                                            if (!used[a42])
                                              if (a[a42] == need42) {
                                                used[a42] = true;
                                                int need13 =
                                                    sum -
                                                    (a[a11] + a[a12] + a[a14]);
                                                for (int a13 = 0; a13 < tot;
                                                     a13++)
                                                  if (!used[a13])
                                                    if (a[a13] == need13) {
                                                      used[a13] = true;
                                                      int need43 =
                                                          sum -
                                                          (a[a41] + a[a42] +
                                                           a[a44]);
                                                      for (int a43 = 0;
                                                           a43 < tot; a43++)
                                                        if (!used[a43])
                                                          if (a[a43] ==
                                                              need43) {
                                                            used[a43] = true;
                                                            for (int a21 = 0;
                                                                 a21 < tot;
                                                                 a21++)
                                                              if (!used[a21]) {
                                                                used[a21] =
                                                                    true;
                                                                int need24 =
                                                                    sum -
                                                                    (a[a21] +
                                                                     a[a22] +
                                                                     a[a23]);
                                                                for (int a24 =
                                                                         0;
                                                                     a24 < tot;
                                                                     a24++)
                                                                  if (!used
                                                                          [a24])
                                                                    if (a[a24] ==
                                                                        need24) {
                                                                      used[a24] =
                                                                          true;
                                                                      int need31 =
                                                                          sum -
                                                                          (a[a11] +
                                                                           a[a21] +
                                                                           a[a41]);
                                                                      for (
                                                                          int a31 =
                                                                              0;
                                                                          a31 <
                                                                          tot;
                                                                          a31++)
                                                                        if (!used
                                                                                [a31])
                                                                          if (a[a31] ==
                                                                              need31) {
                                                                            used[a31] =
                                                                                true;
                                                                            int need34 =
                                                                                sum -
                                                                                (a[a31] +
                                                                                 a[a32] +
                                                                                 a[a33]);
                                                                            for (
                                                                                int a34 =
                                                                                    0;
                                                                                a34 <
                                                                                tot;
                                                                                a34++)
                                                                              if (!used
                                                                                      [a34])
                                                                                if (a[a34] ==
                                                                                    need34) {
                                                                                  used[a34] =
                                                                                      true;
                                                                                  int y[4][4] = {
                                                                                      {a11,
                                                                                       a12,
                                                                                       a13,
                                                                                       a14},
                                                                                      {a21,
                                                                                       a22,
                                                                                       a23,
                                                                                       a24},
                                                                                      {a31,
                                                                                       a32,
                                                                                       a33,
                                                                                       a34},
                                                                                      {a41,
                                                                                       a42,
                                                                                       a43,
                                                                                       a44}};
                                                                                  int x
                                                                                      [4]
                                                                                      [4];
                                                                                  for (
                                                                                      int r =
                                                                                          0;
                                                                                      r <
                                                                                      4;
                                                                                      ++r) {
                                                                                    for (
                                                                                        int c =
                                                                                            0;
                                                                                        c <
                                                                                        4;
                                                                                        ++c) {
                                                                                      x[r]
                                                                                       [c] = a
                                                                                           [y[r]
                                                                                             [c]];
                                                                                    }
                                                                                  }
                                                                                  if (check(
                                                                                          x,
                                                                                          4)) {
                                                                                    cout
                                                                                        << sum
                                                                                        << endl;
                                                                                    for (
                                                                                        int r =
                                                                                            0;
                                                                                        r <
                                                                                        n;
                                                                                        ++r) {
                                                                                      for (
                                                                                          int c =
                                                                                              0;
                                                                                          c <
                                                                                          n;
                                                                                          ++c) {
                                                                                        cout
                                                                                            << x[r]
                                                                                                [c]
                                                                                            << " ";
                                                                                      }
                                                                                      cout
                                                                                          << endl;
                                                                                    }
                                                                                    cout
                                                                                        << endl;
                                                                                    return 0;
                                                                                  }
                                                                                  used[a34] =
                                                                                      false;
                                                                                  break;
                                                                                }
                                                                            used[a31] =
                                                                                false;
                                                                            break;
                                                                          }
                                                                      used[a24] =
                                                                          false;
                                                                      break;
                                                                    }
                                                                used[a21] =
                                                                    false;
                                                              }
                                                            used[a43] = false;
                                                            break;
                                                          }
                                                      used[a13] = false;
                                                      break;
                                                    }
                                                used[a42] = false;
                                                break;
                                              }
                                          used[a12] = false;
                                        }
                                      used[a41] = false;
                                      break;
                                    }
                                used[a32] = false;
                              }
                            used[a23] = false;
                          }
                        used[a14] = false;
                      }
                    used[a44] = false;
                    break;
                  }
              used[a33] = false;
            }
          used[a22] = false;
        }
      used[a11] = false;
    }
}