У вас есть пирамида, состоящая из \(n\) этажей. Этажи пронумерованы сверху вниз. Так как это пирамида, то на \(i\)-м этаже \(i\) комнат.
Будем обозначать \(j\)-ю комнату на \(i\)-м этаже как \((i,j)\). Для всех положительных чисел \(i\) и \(j\) таких, что \(1 \le j \le i < n\), существуют \(2\) односторонние лестницы, ведущие из комнаты \((i,j)\) в \((i+1,j)\), а также из комнаты \((i,j)\) в \((i+1,j+1)\) соответственно.
Вы выбираете для каждой комнаты, разместить там факел или оставить комнату пустой. Определим яркость комнаты \((i, j)\) как количество комнат с факелами, из которых можно попасть в комнату \((i, j)\), используя неотрицательное число лестниц.
Например, если \(n=5\) и факелы расположены в комнатах \((1,1)\), \((2,1)\), \((3,2)\), \((4,1)\), \((4,3)\) и \((5,3)\), то пирамида выглядит следующим образом:
На рисунке выше комнаты с факелами отмечены желтым, пустые — белым. Синие числа в правом нижнем углу показывают яркость комнат.
Комната \((4,2)\) (отмечена звездой на рисунке ниже) имеет яркость \(3\). Комнаты, из которых вы можете попасть в комнату \((4,2)\), имеют красную границу. Яркость равна \(3\), так как в этих комнатах три факела.
Пирамида называется красивой, если и только если для каждого этажа все комнаты на этом этаже имеют одинаковую яркость.
Определим блистательность красивой пирамиды как сумму значений яркости в комнатах \((1,1)\), \((2,1)\), \((3,1)\), ..., \((n,1)\).
Расположите факелы в пирамиде таким образом, чтобы пирамида оказалась красивой, а ее блистательность была максимально возможной.
Можно показать, что ответ всегда существует. Если существуют несколько решений, выведите любое из них.
Выходные данные
Для каждого набора входных данных выведите \(n\) строк — расположение факелов в пирамиде.
В \(i\)-й строке выведите \(i\) чисел, разделенных пробелами. \(j\)-е число в \(i\)-й строке должно быть равно \(1\), если в комнате \((i,j)\) есть факел, и \(0\) иначе.
Можно показать, что ответ всегда существует. Если существуют несколько решений, выведите любое из них.
Примечание
В третьем наборе входных данных факелы размещены в комнатах \((1,1)\), \((2,1)\), \((2,2)\), \((3,1)\) и \((3,3)\).
Пирамида красивая, так как на каждом этаже все комнаты имеют одинаковую яркость. Например, все комнаты на третьем этаже имеют яркость \(3\).
Блистательность пирамиды равна \(1+2+3 = 6\). Можно показать, что не существует расположения факелов для \(n=3\) с большей блистетельностью.