Неоптимальне призначення
Можливо, ви чули про задачу призначення, яка формулюється так: дано n × n матрицю цілих чисел. Необхідно вибрати n елементів так, щоб у кожному рядку і кожному стовпці був вибраний рівно один елемент, а сума вибраних елементів була якомога меншою.
Маленька Міні чула про цю задачу і вважає, що її можна вирішити за допомогою так званого "жадібного алгоритму". Вона думає, що можна вибрати найменший елемент з першого рядка, потім найменший елемент з другого рядка, який не належить вже використаній колонці, і так далі. Якщо в деякому рядку є кілька допустимих найменших елементів, то слід вибрати той, що знаходиться в меншому стовпці.
Її брат Максі розуміє, що це не так. Щоб довести це, він хоче створити матрицю, для якої алгоритм Міні не буде оптимальним. Допоможіть йому в цьому.
Вхідні дані
Одне число n (2 ≤ n ≤ 100).
Вихідні дані
Виведіть цілочисельну матрицю n × n, на якій алгоритм Міні дасть неоптимальне рішення. Якщо такої матриці не існує, виведіть "Impossible". Матриця повинна містити лише невід'ємні числа, що не перевищують 100.