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;
template <class T>
inline bool Up(T &a, const T &b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
inline bool Down(T &a, const T &b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
inline int getus() {
  int tmp, c;
  while (tmp = fgetc(stdin), tmp < '0' || tmp > '9')
    ;
  tmp -= '0';
  while (c = fgetc(stdin), '0' <= c && c <= '9') tmp = tmp * 10 + c - '0';
  return tmp;
}
inline int getint() {
  int tmp, c, flag;
  while (flag = fgetc(stdin), flag != '-' && (flag < '0' || flag > '9'))
    ;
  if (flag == '-')
    tmp = 0;
  else
    tmp = flag - '0';
  while (c = fgetc(stdin), '0' <= c && c <= '9') tmp = tmp * 10 + c - '0';
  return flag == '-' ? -tmp : tmp;
}
int N, s, a[8 * 8];
bool used[8 * 8];
void Brute() {
  int G[8][8];
  s = accumulate(a + 1, a + N * N + 1, 0) / N;
  do {
    int s2 = 0, cnt = 0;
    bool flag = true;
    for (int i = (1); i <= (N); ++i)
      for (int j = (1); j <= (N); ++j) G[i][j] = a[++cnt];
    for (int i = (1); i <= (N); ++i) {
      s2 = 0;
      for (int j = (1); j <= (N); ++j) s2 += G[i][j];
      if (s != s2) {
        flag = false;
        break;
      }
    }
    if (!flag) continue;
    for (int j = (1); j <= (N); ++j) {
      s2 = 0;
      for (int i = (1); i <= (N); ++i) s2 += G[i][j];
      if (s != s2) {
        flag = false;
        break;
      }
    }
    if (!flag) continue;
    s2 = 0;
    for (int i = (1); i <= (N); ++i) s2 += G[i][i];
    if (s != s2) continue;
    s2 = 0;
    for (int i = (1); i <= (N); ++i) s2 += G[i][N - i + 1];
    if (s != s2) continue;
    printf("%d\n", s);
    for (int i = (1); i <= (N); ++i) {
      printf("%d", G[i][1]);
      for (int j = (2); j <= (N); ++j) printf(" %d", G[i][j]);
      putchar('\n');
    }
    break;
  } while (next_permutation(a + 1, a + N * N + 1));
}
void Work() {
  if (N <= 3) {
    Brute();
    return;
  }
  int all = N * N;
  memset(used, 0, sizeof(used));
  s = accumulate(a + 1, a + all + 1, 0) / 4;
  for (int g11 = 1; g11 <= all; ++g11)
    if (!used[g11]) {
      used[g11] = true;
      for (int g22 = 1; g22 <= all; ++g22)
        if (!used[g22]) {
          used[g22] = true;
          for (int g33 = 1; g33 <= all; ++g33)
            if (!used[g33]) {
              used[g33] = true;
              int tmp = s - a[g11] - a[g22] - a[g33];
              for (int g44 = 1; g44 <= all; ++g44)
                if (!used[g44] && a[g44] == (tmp)) {
                  used[g44] = true;
                  for (int g14 = 1; g14 <= all; ++g14)
                    if (!used[g14]) {
                      used[g14] = true;
                      for (int g23 = 1; g23 <= all; ++g23)
                        if (!used[g23]) {
                          used[g23] = true;
                          for (int g32 = 1; g32 <= all; ++g32)
                            if (!used[g32]) {
                              used[g32] = true;
                              int tmp = s - a[g14] - a[g23] - a[g32];
                              for (int g41 = 1; g41 <= all; ++g41)
                                if (!used[g41] && a[g41] == (tmp)) {
                                  used[g41] = true;
                                  for (int g12 = 1; g12 <= all; ++g12)
                                    if (!used[g12]) {
                                      used[g12] = true;
                                      int t1 = s - a[g11] - a[g12] - a[g14];
                                      int t2 = s - a[g12] - a[g22] - a[g32];
                                      int t3 = s - t1 - a[g23] - a[g33];
                                      if (a[g41] + t2 + t3 + a[g44] == s)
                                        for (int g13 = 1; g13 <= all; ++g13)
                                          if (!used[g13] && a[g13] == (t1)) {
                                            used[g13] = true;
                                            for (int g42 = 1; g42 <= all; ++g42)
                                              if (!used[g42] &&
                                                  a[g42] == (t2)) {
                                                used[g42] = true;
                                                for (int g43 = 1; g43 <= all;
                                                     ++g43)
                                                  if (!used[g43] &&
                                                      a[g43] == (t3)) {
                                                    used[g43] = true;
                                                    for (int g21 = 1;
                                                         g21 <= all; ++g21)
                                                      if (!used[g21]) {
                                                        used[g21] = true;
                                                        int p1 = s - a[g21] -
                                                                 a[g22] -
                                                                 a[g23];
                                                        int p2 = s - a[g11] -
                                                                 a[g21] -
                                                                 a[g41];
                                                        int p3 = s - p2 -
                                                                 a[g32] -
                                                                 a[g33];
                                                        if (a[g14] + p1 + p3 +
                                                                a[g44] ==
                                                            s)
                                                          for (int g24 = 1;
                                                               g24 <= all;
                                                               ++g24)
                                                            if (!used[g24] &&
                                                                a[g24] ==
                                                                    (p1)) {
                                                              used[g24] = true;
                                                              for (int g31 = 1;
                                                                   g31 <= all;
                                                                   ++g31)
                                                                if (!used
                                                                        [g31] &&
                                                                    a[g31] ==
                                                                        (p2)) {
                                                                  used[g31] =
                                                                      true;
                                                                  for (int g34 =
                                                                           1;
                                                                       g34 <=
                                                                       all;
                                                                       ++g34)
                                                                    if (!used
                                                                            [g34] &&
                                                                        a[g34] ==
                                                                            (p3)) {
                                                                      used[g34] =
                                                                          true;
                                                                      printf(
                                                                          "%d"
                                                                          "\n",
                                                                          s);
                                                                      printf(
                                                                          "%d "
                                                                          "%d "
                                                                          "%d "
                                                                          "%d"
                                                                          "\n",
                                                                          a[g11],
                                                                          a[g12],
                                                                          a[g13],
                                                                          a[g14]);
                                                                      printf(
                                                                          "%d "
                                                                          "%d "
                                                                          "%d "
                                                                          "%d"
                                                                          "\n",
                                                                          a[g21],
                                                                          a[g22],
                                                                          a[g23],
                                                                          a[g24]);
                                                                      printf(
                                                                          "%d "
                                                                          "%d "
                                                                          "%d "
                                                                          "%d"
                                                                          "\n",
                                                                          a[g31],
                                                                          a[g32],
                                                                          a[g33],
                                                                          a[g34]);
                                                                      printf(
                                                                          "%d "
                                                                          "%d "
                                                                          "%d "
                                                                          "%d"
                                                                          "\n",
                                                                          a[g41],
                                                                          a[g42],
                                                                          a[g43],
                                                                          a[g44]);
                                                                      return;
                                                                      used[g34] =
                                                                          false;
                                                                    }
                                                                  used[g31] =
                                                                      false;
                                                                }
                                                              used[g24] = false;
                                                            }
                                                        used[g21] = false;
                                                      }
                                                    used[g43] = false;
                                                  }
                                                used[g42] = false;
                                              }
                                            used[g13] = false;
                                          }
                                      used[g12] = false;
                                    }
                                  used[g41] = false;
                                }
                              used[g32] = false;
                            }
                          used[g23] = false;
                        }
                      used[g14] = false;
                    }
                  used[g44] = false;
                }
              used[g33] = false;
            }
          used[g22] = false;
        }
      used[g11] = false;
    }
}
void Init() {
  scanf("%d", &N);
  for (int i = (1); i <= (N * N); ++i) scanf("%d", a + i);
  sort(a + 1, a + N * N + 1);
}
int main() {
  Init();
  Work();
  return 0;
}