## COCI '20 Contest 4 #3 Hop

View as PDF

Points: 25 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type

There are water lilies, numbered through , in a line. On the lily there is a positive integer , and the sequence is strictly increasing.

Enter three frogs.

Every pair of water lilies , where , must belong to frog , frog , or frog .

A frog can hop from water lily to water lily if the pair belongs to it, and divides .

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

#### Input Specification

The first line contains a positive integer , the number of water lilies.

The second line contains positive integers , the numbers on the water lilies.

#### Output Specification

Output lines. In the line, output numbers, where the number is the label of the frog to which belongs.

#### Constraints

If in your solution some frog can make consecutive hops, where , but no frog can make consecutive hops, your score for that test case is points, where

and is the number of points for that subtask.

The score for some subtask equals the minimum score which your solution gets over all test cases in that subtask.

#### Sample Input 1

8
3 4 6 9 12 18 36 72

#### Sample Output 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

#### Explanation

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

The blue frog can hop from water lily to water lily , then to water lily , and then to . These are the only three consecutive hops any frog can make.

The green frog can hop from water lily to water lily , and then to , because divides , and divides . Those are two consecutive hops.

The red frog cannot hop from water lily to water lily because is not divisible by .

No frog can make more than three consecutive hops.

#### Sample Input 2

2
10 101

#### Sample Output 2

1