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 N = 4;
int n, a[N * N];
bool used[N * 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];
  }
  return A == sum && B == sum;
}
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];
    if (check(x, n)) {
      int sum = 0;
      for (int i = 0; i < n; ++i) sum += x[0][i];
      printf("%d\n", sum);
      for (int r = 0; r < n; ++r)
        for (int c = 0; c < n; ++c) printf("%d%c", x[r][c], " \n"[c == n - 1]);
      return;
    }
  } while (next_permutation(a, a + n * n));
}
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n * n; ++i) {
    scanf("%d", a + i);
  }
  if (n <= 3) {
    work3();
    return 0;
  }
  int sum = 0;
  for (int i = 0; i < n * n; ++i) sum += a[i];
  sum /= n;
  int tot = n * n;
  for (int a11 = 0; a11 < tot; ++a11)
    if (!used[a11]) {
      used[a11] = 1;
      for (int a22 = 0; a22 < tot; ++a22)
        if (!used[a22]) {
          used[a22] = 1;
          for (int a33 = 0; a33 < tot; ++a33)
            if (!used[a33]) {
              used[a33] = 1;
              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] = 1;
                    for (int a14 = 0; a14 < tot; ++a14)
                      if (!used[a14]) {
                        used[a14] = 1;
                        for (int a23 = 0; a23 < tot; ++a23)
                          if (!used[a23]) {
                            used[a23] = 1;
                            for (int a32 = 0; a32 < tot; ++a32)
                              if (!used[a32]) {
                                used[a32] = 1;
                                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] = 1;
                                      for (int a12 = 0; a12 < tot; ++a12)
                                        if (!used[a12]) {
                                          used[a12] = 1;
                                          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] = 1;
                                                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] = 1;
                                                      int need43 =
                                                          sum -
                                                          (a[a13] + a[a23] +
                                                           a[a33]);
                                                      for (int a43 = 0;
                                                           a43 < tot; ++a43)
                                                        if (!used[a43])
                                                          if (a[a43] ==
                                                              need43) {
                                                            used[a43] = 1;
                                                            for (int a21 = 0;
                                                                 a21 < tot;
                                                                 ++a21)
                                                              if (!used[a21]) {
                                                                used[a21] = 1;
                                                                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] =
                                                                          1;
                                                                      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] =
                                                                                1;
                                                                            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] =
                                                                                      1;
                                                                                  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)) {
                                                                                    printf(
                                                                                        "%d\n",
                                                                                        sum);
                                                                                    for (
                                                                                        int r =
                                                                                            0;
                                                                                        r <
                                                                                        n;
                                                                                        ++r)
                                                                                      for (
                                                                                          int c =
                                                                                              0;
                                                                                          c <
                                                                                          n;
                                                                                          ++c)
                                                                                        printf(
                                                                                            "%d%c",
                                                                                            x[r]
                                                                                             [c],
                                                                                            " \n"
                                                                                                [c ==
                                                                                                 n - 1]);
                                                                                    return 0;
                                                                                  }
                                                                                  used[a34] =
                                                                                      0;
                                                                                  break;
                                                                                }
                                                                            used[a31] =
                                                                                0;
                                                                            break;
                                                                          }
                                                                      used[a24] =
                                                                          0;
                                                                      break;
                                                                    }
                                                                used[a21] = 0;
                                                              }
                                                            used[a43] = 0;
                                                            break;
                                                          }
                                                      used[a13] = 0;
                                                      break;
                                                    }
                                                used[a42] = 0;
                                                break;
                                              }
                                          used[a12] = 0;
                                          break;
                                        }
                                      used[a41] = 0;
                                      break;
                                    }
                                used[a32] = 0;
                              }
                            used[a23] = 0;
                          }
                        used[a14] = 0;
                      }
                    used[a44] = 0;
                    break;
                  }
              used[a33] = 0;
            }
          used[a22] = 0;
        }
      used[a11] = 0;
    }
  return 0;
}