Полностью ненулевой определитель

Дано целое число n. Требуется построить n×n матрицу M, состоящую из нулей и единиц, так чтобы для каждого 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 целых чисел (нули или единицы), разделенных пробелами.

Примеры