eolymp
bolt
Try our new interface for solving problems
Problems

Граф-турнир

Граф-турнир

Time limit 1 second
Memory limit 256 MiB

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

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

Input data

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

Output data

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

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

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

  • a_{v,u} + a_{u,v} = 1 для всех v, u (1v, un, vu);

  • a_{v,v} = 0 для всех v (1vn).

Examples

Input example #1
3
Output example #1
0 1 0
0 0 1
1 0 0
Source Winter School Kharkov 2013, Day 6 - G.Agapov and I.Fefer