У вас есть пирамида, состоящая из $$$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)$$$.

Расположите факелы в пирамиде таким образом, чтобы пирамида оказалась красивой, а ее блистательность была максимально возможной.

Можно показать, что ответ всегда существует. Если существуют несколько решений, выведите любое из них.