Nonoptimal Assignments
You might have heard about assignment problem, stated as follows. Given n × n matrix of integer numbers, one has to choose n elements of the matrix, so that for each row and each column exactly one element is selected from it, and the sum of the selected elements is minimal possible.
Little Mini has just heard about the problem and thinks that it can be solved using so called "greedy algorithm". That is, she thinks that it is possible to take the smallest element from the first row, after that take minimal element from the second row, that does not belong to the column that was already used, and so on. Each time if there are several possible elements, the one from the smallest column is used.
Her brother Maxi understands that it is not true. To prove it, he wants to construct a matrix where Mini's assignment would be non-optimal. Help him to do so.
Input
One integer n (2 ≤ n ≤ 100).
Output
Output n × n matrix of integer numbers where Mini's algorithm would not find the optimal assignment. If no such matrix exists, output "Impossible" instead. Matrix must contain only non-negative integer numbers not exceeding 100.