Cow Partitioning in Wisconsin

In \(Wisconsin\), there are \(3\times k\) cities numbered \(1,2,\ldots,3k\). Each city has exactly \(1000\) cows. Jersey owns \(w_1,w_2,\ldots,w_{3k}\) cows in these cities, where \(0\le w_i\le 1000\). Since every city has \(1000\) cows, when the cities are partitioned equally into 3 groups (each containing exactly \(k\) cities), each group has a total of \(1000\times k\) cows.

Your task is to partition the cities into 3 groups (each group containing exactly \(k\) cities) such that in at least two groups the total number of cows owned by Jersey is strictly greater than \(\frac{1000\times k}{2}\) (i.e. \(500\times k\)). It is guaranteed that the input instance has a valid solution. If there are multiple answers, output any one of them.

Input Format (Latex):
\( k \)
\( w_1,w_2,\ldots,w_{3k} \)

Output Format (Latex):
Output a sequence of \(3k\) integers where the \(i\)-th integer indicates the group number (1, 2, or 3) of the \(i\)-th city. Each group must contain exactly \(k\) cities, and the partition must satisfy the above condition.

inputFormat

The first line contains an integer \(k\). The next line contains \(3k\) integers \(w_1, w_2, \ldots, w_{3k}\), where \(0 \le w_i \le 1000\).

outputFormat

Output a single line containing \(3k\) integers separated by spaces. The \(i\)-th integer (either 1, 2, or 3) represents the group to which the \(i\)-th city is assigned. Each group must have exactly \(k\) cities, and the partition must ensure that in at least two groups, the total owned cows are greater than \(500 \times k\).

sample

1
600 600 400

1 2 3