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^{2}` 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

`on the first line.`

**N**`numbers separated by spaces on the second line.`

**N**^{2}## Output

`lines of`

**N**`space-separated numbers each.`

**N**## Constraints

`≤ 100`

**N**## Sample

Input | Output |
---|---|

338 45 20 64 48 6 45 59 55 | 64 6 4538 59 45 20 48 55 |

A simple solution is to sort the numbers, then place the greatest

`n`numbers on the main diagonal. The other numbers can be placed in any order.# C++ solution (Marius Gavrilescu)

1 #include <cstdio> 2 #include <algorithm> 3 #include <functional> 4 5 int v[10005]; 6 7 int main(void){ 8 int n; 9 scanf("%d", &n); 10 for(int i = 0 ; i < n * n ; i++) 11 scanf("%d", v + i); 12 std::sort(v, v + n * n, std::greater<int>()); 13 14 int p = n; 15 for(int i = 0 ; i < n ; i++) { 16 for(int j = 0 ; j < n ; j++) 17 printf("%d ", i == j ? v[i] : v[p++]); 18 puts(""); 19 } 20 return 0; 21 }

# Perl soluton (Marius Gavrilescu)

1 #!/usr/bin/perl 2 use v5.14; 3 use warnings; 4 5 my $n = <>; 6 my @v = sort { $b <=> $a } split ' ', <>; 7 my $p = $n; 8 9 for my $i (1 .. $n) { 10 for my $j (1 .. $n) { 11 print $i == $j ? $v[$i - 1] : $v[$p++], ' ' 12 } 13 say ''; 14 }