We have a special evening planned for you tonight... filled with fifty shades of problem solving! There are two types of matrices: the domimatrices, which have maximum traces, and the submatrices, with smaller traces.

Given N² numbers, can you whip up a domimatrix? Since you've been on your best behaviour so far, here's a little hint to make you come up with the answer faster: the trace of a matrix is the sum of the numbers on its primary diagonal (in other words, Tr_A is A_1,1 + A_2,2 + ... + A_N,N).

Input

N on the first line.
N² numbers separated by spaces on the second line.

Output

N lines of N space-separated numbers each.

Constraints

N ≤ 100

Sample

Input	Output
3 38 45 20 64 48 6 45 59 55	64 6 45 38 59 45 20 48 55