E. Визуализируй это
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Айдар, Бегимай и Виктор для решения сложной задачи написали своё первое дерево отрезков.

Но возникла проблема — их дерево выдавало неверные ответы даже на тестовых примерах из условия задачи.

В первую очередь, ребята предположили, что они неверно сопоставили полуинтервалы массива узлам. Виктор сказал, что надо вывести по порядку все узлы и их полуинтервалы.

Бегимай на это заметила, что простой построчный вывод не сильно ускорит процесс — надо визуализировать всё дерево целиком!

Внимание: Данная задача использует определённые правила построения дерева отрезков — ознакомьтесь с ними в примечании к задаче.

Входные данные

В первой строке дано целое число $$$n$$$ $$$(1 \le n \le 10^4)$$$ — размер массива.

Выходные данные

Дерево необходимо визуализировать по слоям, каждому слою соответствует одна строка.

  • Корень дерева визуализируется в первой строке.
  • Дочерние узлы располагаются на строку ниже от родительского узла.
  • Каждый узел визуализируется следующим образом:
    • Полуинтервал узла описывается в формате $$$[L;R)$$$.
    • В случае, если $$$L + 1 \lt R$$$, строго под знаком «;» вплоть до самой нижней строки располагаются символы «|», обозначающие разделитель между левым и правым поддеревьями.
    • Между строкой, описывающей сам узел, и любым разделителем на той же строке должно располагаться минимально возможное количество пробелов (не менее одного).
  • Хотя бы одна строка вывода не должна начинаться с пробела.
  • Последний символ каждой строки не должен являться пробелом.

Ознакомьтесь с тестовыми примерами для уточнения подробностей.

Примеры
Входные данные
1
Выходные данные
[0;1)
Входные данные
2
Выходные данные
    [0;2)
[0;1) | [1;2)
Входные данные
3
Выходные данные
    [0;3)
[0;1) |     [1;3)
      | [1;2) | [2;3)
Входные данные
7
Выходные данные
                    [0;7)
    [0;3)             |             [3;7)
[0;1) |     [1;3)     |     [3;5)     |     [5;7)
      | [1;2) | [2;3) | [3;4) | [4;5) | [5;6) | [6;7)
Входные данные
9
Выходные данные
                            [0;9)
            [0;4)             |             [4;9)
    [0;2)     |     [2;4)     |     [4;6)     |     [6;9)
[0;1) | [1;2) | [2;3) | [3;4) | [4;5) | [5;6) | [6;7) |     [7;9)
      |       |       |       |       |       |       | [7;8) | [8;9)
Примечание

Определение

Дерево отрезков, построенное для массива длины $$$n$$$, представляет из себя бинарное дерево, в котором каждый узел сопоставлен какому-либо полуинтервалу данного массива:

  • Корень дерева сопоставлен всему массиву — полуинтервалу $$$[0; n)$$$.
  • Каждый лист (терминальный узел) дерева сопоставлен определённому элементу массива — полуинтервалу $$$[i; i + 1)$$$.
  • Общее правило сопоставления узлов и полуинтервалов следующее:
    • Пусть нетерминальный узел $$$v$$$ сопоставлен полуинтервалу $$$[L; R)$$$.
    • Пусть $$$M = \lfloor\frac{(L + R)}{2}\rfloor$$$ — середина полуинтервала.
    • В таком случае левый сын данного узла сопоставлен полуинтервалу $$$[L, M)$$$, а правый сын — полуинтервалу $$$[M; R)$$$.