Повністю ненульовий визначник

Дано ціле число n. Потрібно побудувати матрицю розміром n×n, що складається з нулів та одиниць, таку, що для кожного m, де 1 ≤ m ≤ n, і кожного a, де 1 ≤ a ≤ n-m+1, підматриця, утворена рядками від 1 до m та стовпцями від a до a+m-1 матриці M, є неособливою над полем F_2.

Нагадаємо, що матриця m×m P над полем F_2 є неособливою, якщо існує непарна кількість перестановок p чисел 1, 2, ..., m, таких що елементи P_{1, p1}, P_{2, p2}, ..., P_{m, pm} всі дорівнюють одиниці.

Вхідні дані

Перший і єдиний рядок вхідного файлу містить ціле число n, де 1 ≤ n ≤ 100.

Вихідні дані

Виведіть потрібну матрицю у вигляді n рядків по n цілих чисел (нулів або одиниць) у кожному, розділених пробілами всередині рядка.

Приклади