B. Граф-турнир
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В данной задаче от Вас требуется построить граф-турнир, состоящий из n вершин, такой, что для любой ориентированной пары вершин (v, u)(v ≠ u) существует путь из вершины v в вершину u длины не более двух ребер.

Ориентированный граф без петель называется турниром, если между любыми его двумя различными вершинами есть ровно одно ребро (в одном из двух возможных направлений).

Входные данные

В первой строке записано единственное целое число n (3 ≤ n ≤ 1000) — количество вершин графа.

Выходные данные

Выведите -1, если не существует ни одного графа, удовлетворяющего описанным условиям.

Иначе выведите n строк, в каждой строке по n целых чисел, разделенных пробелами, — матрицу смежности a найденного турнира. Считайте, что вершины графа пронумерованы целыми числами от 1 до n. Тогда av, u = 0, если в турнире нет ребра из вершины v в вершину u, и av, u = 1, если ребро есть.

Так как выведенный граф должен быть турниром, то должны выполняться следующие равенства:

  • av, u + au, v = 1 для всех v, u (1 ≤ v, u ≤ n; v ≠ u);
  • av, v = 0 для всех v (1 ≤ v ≤ n).
Примеры
Входные данные
3
Выходные данные
0 1 0
0 0 1
1 0 0
Входные данные
4
Выходные данные
-1