시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 4 3 3 75.000%

문제

♪ 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 xi, and the sequence (xi)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 xi divides xj.

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 xi (1 ≤ xi ≤ 1018), 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.

예제 입력 1

8
3 4 6 9 12 18 36 72

예제 출력 1

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

2
10 101

예제 출력 2

1

힌트

Clarification of the first example:

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

The blue frog can hop from water lily x1 = 3 to water lily x4 = 9, then to water lily x7 = 36, and then to x8 = 72. These are the only three consecutive hops any frog can make.

The green frog can hop from water lily x2 = 4 to water lily x5 = 12, and then to x7 = 36, because 4 divides 12, and 12 divides 36. Those are two consecutive hops.

The red frog cannot hop from water lily x2 = 4 to water lily x3 = 6 because 6 is not divisible by 4.

No frog can make more than three consecutive hops.