A1607.[COCI-2020-2021-contest4]#1 Hop
普及/提高-
通过率：0%
时间限制：1.00s
内存限制：128MB
题目描述
♪ 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 7
输出#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
说明/提示
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.