20662번 - Hop 스페셜 저지출처다국어분류

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

There are n water lilies, numbered 1 through n, in a line. On the i-th lily there is a positive integer x_i, and the sequence (x_i)_1≤i≤n is strictly increasing.

Enter three frogs.

Every pair of water lilies (a, b), where a < b, must belong to frog 1, frog 2, or frog 3.

A frog can hop from water lily i to water lily j > i if the pair (i, j) belongs to it, and x_i divides x_j.

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

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

The second line contains n positive integers x_i (1 ≤ x_i ≤ 10¹⁸), the numbers on the water lilies.

Output n − 1 lines. In the i-th line, output i numbers, where the j-th number is the label of the frog to which (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₁ = 3 to water lily x₄ = 9, then to water lily x₇ = 36, and then to x₈ = 72. These are the only three consecutive hops any frog can make.

The green frog can hop from water lily x₂ = 4 to water lily x₅ = 12, and then to x₇ = 36, because 4 divides 12, and 12 divides 36. Those are two consecutive hops.

The red frog cannot hop from water lily x₂ = 4 to water lily x₃ = 6 because 6 is not divisible by 4.

No frog can make more than three consecutive hops.