Average Score

2000ms

262144K

Description:

After the educational reform Polycarp studies only two subjects at school, Safety Studies and PE (Physical Education). During the long months of the fourth term, he received n marks in them. When teachers wrote a mark in the journal, they didn't write in what subject the mark was for, they just wrote the mark.

Now it's time to show the journal to his strict parents. Polycarp knows that recently at the Parent Meeting the parents were told that he received a Safety Studies marks and b PE marks (a + b = n). Now Polycarp wants to write a subject's name in front of each mark so that:

there are exactly a Safety Studies marks,
there are exactly b PE marks,
the total average score in both subjects is maximum.

An average subject grade is the sum of all marks in it, divided by the number of them. Of course, the division is performed in real numbers without rounding up or down. Polycarp aims to maximize the x₁ + x₂, where x₁ is the average score in the first subject (Safety Studies), and x₂ is the average score in the second one (Physical Education).

Input:

The first line contains an integer n (2 ≤ n ≤ 10⁵), n is the number of marks in Polycarp's Journal. The second line contains two positive integers a, b (1 ≤ a, b ≤ n - 1, a + b = n). The third line contains a sequence of integers t₁, t₂, ..., t_n (1 ≤ t_i ≤ 5), they are Polycarp's marks.

Output:

Print the sequence of integers f₁, f₂, ..., f_n, where f_i (1 ≤ f_i ≤ 2) is the number of a subject to which the i-th mark should be attributed. If there are several possible solutions, then print such that the sequence f₁, f₂, ..., f_n is the smallest lexicographically.

The sequence p₁, p₂, ..., p_n is lexicographically less than q₁, q₂, ..., q_n if there exists such j (1 ≤ j ≤ n) that p_i = q_i for all 1 ≤ i < j, аnd p_j < q_j.

Sample Input:

5
3 2
4 4 5 4 4

Sample Output:

1 1 2 1 2

Sample Input:

4
2 2
3 5 4 5

Sample Output:

1 1 2 2

Sample Input:

6
1 5
4 4 4 5 4 4

Sample Output:

2 2 2 1 2 2

Note:

In the first sample the average score in the first subject is equal to 4, and in the second one — to 4.5. The total average score is 8.5.

Informação

Provedor Codeforces

Código CF81C