Футбольная лига недавно стартовала в Красивой долине. Всего \(n\) команд участвует в этой лиге. Пронумеруем их для удобства целыми числами от \(1\) до \(n\).
Всего будет проведено ровно \(\frac{n(n-1)}{2}\) матчей: каждая команда будет играть со всеми оставшимися командами ровно по одному разу. В каждом матче всегда есть победившая и проигравшая команда, ничьих не бывает.
После того, как все матчи будут сыграны, организаторы посчитают количество красивых троек. Тройка команд \((A, B, C)\) называется красивой, если команда \(A\) победила команду \(B\), команда \(B\) победила команду \(C\) и команда \(C\) победила команду \(A\). Мы рассматриваем только тройки различных команд, порядок команд внутри тройки имеет значение.
Красотой лиги назовем количество красивых троек.
В данный момент, \(m\) матчей уже было проведено и их результаты уже известны.
Какая максимальная красота лиги может быть в итоге, после проведения оставшихся матчей? Также найдите возможные результаты оставшихся \(\frac{n(n-1)}{2} - m\) матчей, при которых красота лиги максимально возможная.
Выходные данные
Выведите \(n\) строк, в каждой из них строку, содержащую ровно \(n\) символов. Каждый символ должен быть равен \(0\) или \(1\).
Обозначим за \(a_{ij}\) \(j\)-е число в \(i\)-й строке. Для всех \(1 \leq i \leq n\) должно быть выполнено \(a_{ii} = 0\). Для всех пар команд \(i \neq j\) число \(a_{ij}\) обозначает результат матча между командой с номером \(i\) и командой с номером \(j\):
- Если \(a_{ij}\) это \(1\), то \(i\)-я команда победила \(j\)-ю команду;
- Иначе \(j\)-я команда победила \(i\)-ю команду;
- Также, должно быть выполнено, что \(a_{ij} + a_{ji} = 1\).
Также заметьте, что результаты \(m\) матчей, которые уже были сыграны, не могут быть изменены в вашей лиге.
Красота лиги, представленной в качестве ответа должна быть максимально возможной. Если существует несколько лиг, подходящих под условия и красота которых максимальна, вы можете найти любую из них.
Примечание
Красота лиги в первом тесте равна \(3\), потому что есть ровно три красивые тройки команд: \((1, 2, 3)\), \((2, 3, 1)\), \((3, 1, 2)\).
Красота лиги во втором тесте равна \(6\) потому что существует шесть красивых троек команд: \((1, 2, 4)\), \((2, 4, 1)\), \((4, 1, 2)\), \((2, 4, 3)\), \((4, 3, 2)\), \((3, 2, 4)\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 1
1 2
|
010
001
100
|
|
2
|
4 2
1 2
1 3
|
0110
0001
0100
1010
|