Скоро состоится большой футбольный чемпионат! \(n\) команд будут участвовать в нем, и каждая пара различных команд сыграет ровно один матч друг с другом.
У матча может быть два различных исхода:
- матч может закончиться вничью, тогда обе команды получат по \(1\) очку;
- одна из команд может победить, тогда победившая команда получит \(3\) очка, а проигравшая — \(0\).
Счет команды — суммарное количество очков, полученное командой за все матчи, в которых она играла.
Вас интересует гипотетическая ситуация, в которой все команды будут в конце чемпионата иметь одинаковый счет. Простой пример такой ситуации — если все матчи закончатся вничью, но вас интересует подобная ситуация с минимально возможным количеством ничьих.
Ваша задача — найти ситуацию (выбрать результат каждой игры), в которой у всех команд одинаковый итоговый счет, а количество ничьих минимально возможно.
Выходные данные
Для каждого набора входных данных выведите \(\frac{n(n - 1)}{2}\) целых чисел, описывающих результаты игр в следующем порядке: первое число соответствует результату матча между командой \(1\) и командой \(2\), второе — между командой \(1\) и командой \(3\), затем \(1\) и \(4\), ..., \(1\) и \(n\), \(2\) и \(3\), \(2\) и \(4\), ..., \(2\) и \(n\), и так далее, до результата матча между командой \(n - 1\) и командой \(n\).
Число, соответствующее результату матча между командой \(x\) и командой \(y\), должно быть равно \(1\), если побеждает команда \(x\), \(-1\), если побеждает команда \(y\), или \(0\), если матч заканчивается вничью.
Все команды должны иметь одинаковый итоговый счет, и количество ничьих должно быть минимально возможным. Если оптимальных ответов несколько — выведите любой из них. Можно показать, что всегда есть способ составить результаты игр так, что все команды имеют одинаковый итоговый счет.
Примечание
В первом наборе входных данных из примера обе команды получают по \(1\) очку, так как их матч заканчивается вничью.
Во втором наборе входных данных из примера команда \(1\) побеждает команду \(2\) (команда \(1\) получает \(3\) очка), команда \(1\) проигрывает команде \(3\) (команда \(3\) получает \(3\) очка), и команда \(2\) выигрывает у команды \(3\) (команда \(2\) получает \(3\) очка).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
2
3
|
0
1 -1 1
|