E. Visualize This
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Aidar, Begimai, and Viktor wrote their first segment tree to solve a complex problem.

However, a problem arose — their tree was producing incorrect answers even for the test cases provided in the problem statement.

First of all, the guys assumed that they had incorrectly matched the semi-intervals of the array to the nodes. Viktor suggested that they should output all the nodes and their semi-intervals in order.

Begimai noted that simple line-by-line output would not significantly speed up the process — they needed to visualize the entire tree!

Attention: This problem uses certain rules for constructing a segment tree — familiarize yourself with them in the notes of the problem.

Input

The first line contains an integer $$$n$$$ $$$(1 \le n \le 10^4)$$$ — the size of the array.

Output

The tree must be visualized layer by layer, with each layer corresponding to one line.

  • The root of the tree is visualized in the first line.
  • Child nodes are placed one line below their parent node.
  • Each node is visualized as follows:
    • The semi-interval of the node is described in the format $$$[L;R)$$$.
    • In case $$$L + 1 \lt R$$$, strictly under the symbol ";" down to the very last line, there should be "|" symbols representing the separator between the left and right subtrees.
    • There must be a minimally possible number of spaces (at least one) between the line describing the node itself and any separator on the same line.
  • At least one output line must not start with a space.
  • The last character of each line must not be a space.

Refer to the test examples for clarification on the details.

Examples
Input
1
Output
[0;1)
Input
2
Output
    [0;2)
[0;1) | [1;2)
Input
3
Output
    [0;3)
[0;1) |     [1;3)
      | [1;2) | [2;3)
Input
7
Output
                    [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)
Input
9
Output
                            [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)
Note

Definition

A segment tree built for an array of length $$$n$$$ represents a binary tree in which each node is matched to a certain semi-interval of the given array:

  • The root of the tree is matched to the entire array — the semi-interval $$$[0; n)$$$.
  • Each leaf (terminal node) of the tree is matched to a specific element of the array — the semi-interval $$$[i; i + 1)$$$.
  • The general rule for matching nodes and semi-intervals is as follows:
    • Let the non-terminal node $$$v$$$ be matched to the semi-interval $$$[L; R)$$$.
    • Let $$$M = \lfloor\frac{(L + R)}{2}\rfloor$$$ — the midpoint of the semi-interval.
    • In this case, the left child of this node is matched to the semi-interval $$$[L, M)$$$, and the right child is matched to the semi-interval $$$[M; R)$$$.