Description

There are $n$ lily pads, numbered from $1$ to $n$ in order. On the $i$-th pad there is an integer $x_i$, and the sequence $(x_i)_{1 \le i \le n}$ is strictly increasing.

Three frogs arrive.

Every pair of lily pads $(a,b)$ with $a \lt b$ must be assigned to exactly one of frogs $1,2,$ or $3$.

If a pair $(i,j)$ is assigned to a frog and $x_j$ is divisible by $x_i$ ($j \gt i$), then that frog can jump from pad $i$ to pad $j$.

Find an assignment such that no frog can make more than $3$ consecutive jumps.

Input Format

The first line contains a positive integer $n$, the number of lily pads.

The second line contains $n$ positive integers $x_i$, the integers on the lily pads.

Output Format

Output $n-1$ lines. On line $i$, output $i$ integers, where the $j$-th integer on that line indicates which frog the pair $(j,i+1)$ is assigned to.

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

Hint

Explanation of Sample 1

Frogs $1,2,3$ are represented by blue, green, and red, respectively.

The blue frog can jump from $x_1=3$ to $x_4=9$, then to $x_7=36$, and then to $x_8=72$. This frog can make only $3$ consecutive jumps.

The green frog can jump from $x_2=4$ to $x_5=12$, and then to $x_7=36$. This frog can make only $2$ consecutive jumps.

The red frog cannot jump from $x_2=4$ to $x_3=6$, because $6$ is not divisible by $4$.

Constraints

This problem uses bundled evaluation.

Subtask	Points	Constraints and notes
$1$	$10$	$n \le 30$
$2$	$100$	None

For $100\%$ of the testdata, $1 \le n \le 1000$, $1 \le x_i \le 10^{18}$.

Scoring

In your output, if one frog can make $k$ consecutive jumps with $k \gt 3$, and no frog can make $k+1$ consecutive jumps, then the score for that test point is $f(k)·x$ points, where:

$$f(k)=\dfrac{1}{10}· \begin{cases} 11-k & (4 \le k \le 5) \cr 8-\lfloor {\dfrac{k}{2}} \rfloor & (6 \le k \le 11) \cr 1 & (12 \le k \le 19) \cr 0 & (k \ge 20) \cr \end{cases}$$

Here, $x$ is the total score of the corresponding subtask. The score of each subtask equals the minimum score among all test points in that subtask.

Because the scoring of this problem is special, a non-official self-written Special Judge is enabled. You can also download it from the attachments. Everyone is welcome to hack (you may send a private message or post directly).

Notes

The points of this problem follow the original COCI setting, with a full score of $110$.

Translated from COCI2020-2021 CONTEST #4 T3 Hop.

Translated by ChatGPT 5