Hop

문제

♪ Jeremiah was a bullfrog Was a good friend of mine ♪

There are n water lilies, numbered $11$ through $nn$, in a line. On the $ii$-th lily there is a positive integer $x_{i}x\_i$, and the sequence (x_i)_{1 ≤ i ≤ n} is strictly increasing.

Enter three frogs.

Every pair of water lilies $(a,b)(a,\; b)$, where , must belong to frog $11$, frog $22$, or frog $33$.

A frog can hop from water lily $ii$ to water lily $j>ij\; >\; i$ if the pair $(i,j)(i,\; j)$ belongs to it, and $x_{i}x\_i$ divides $x_{j}x\_j$.

Distribute the pairs among the frogs such that no frog can make more than $33$ consecutive hops.

입력

The first line contains a positive integer $nn$ (1 ≤ n ≤ 1000), the number of water lilies.

The second line contains $nn$ positive integers $x_{i}x\_i$ (1 ≤ x_i ≤ 10^{18}), the numbers on the water lilies.

출력

Output $n-1n\; -\; 1$ lines. In the $ii$-th line, output $ii$ numbers, where the $jj$-th number is the label of the frog to which $(j,i+1)(j,\; i\; +\; 1)$ belongs.

힌트

Clarification of the first example:

The frogs are marked blue (1), green (2), and red (3).

The blue frog can hop from water lily $x_1=3x\_1\; =\; 3$ to water lily $x_4=9x\_4\; =\; 9$, then to water lily $x_7=36x\_7\; =\; 36$, and then to $x_8=72x\_8\; =\; 72$. These are the only three consecutive hops any frog can make.

The green frog can hop from water lily $x_2=4x\_2\; =\; 4$ to water lily $x_5=12x\_5\; =\; 12$, and then to $x_7=36x\_7\; =\; 36$, because $44$ divides $1212$, and $1212$ divides $3636$. Those are two consecutive hops.

The red frog cannot hop from water lily $x_2=4x\_2\; =\; 4$ to water lily $x_3=6x\_3\; =\; 6$ because $66$ is not divisible by $44$.

No frog can make more than three consecutive hops.

8
3 4 6 9 12 18 36 72

1
2 3
1 2 3
1 2 3 1
2 3 1 2 3
1 2 3 1 2 3
1 2 3 1 2 3 1

2
10 101

1