Fruit Ninja

Time Limit: 3 Seconds    Memory Limit: 131072 KB

Almost all of you are familiar with the famous game “Fruit Ninja”. This time a ninja comes to buy some fruits to play with. He has two bags with capacity of a and b fruits (first bag can be loaded with at most a fruits and the second bag with at most b fruits). There are n fruits with different weights of w_i (1 <= i <= n) and a + b = n. As ninjas must be so fast in moving, our ninja wants to load all of these n fruits in his bags so that the sum of average weights of two bags minimizes.

Input

For each test case, first line contains an integer n (2 <= n <= 1005), total number of fruits. 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 w₁, ..., w_n (1 <= w_i <= 10⁶), weight of each fruit. Input ends with 0 for parameter n.

Output

For each test case, print the sequence of integers f₁, ..., f­n­, where f_i (1 <= f_i <= 2) is the number of the bag in which the ith fruit should be loaded in a line. 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
4
2 2
3 5 4 5
6
2 4
5 4 4 5 4 4
0

Sample Output

1 1 1 2 2
1 1 2 2
2 1 1 2 2 2

Submit