The package for this problem was not updated by the problem writer or Codeforces administration after we've upgraded the judging servers. To adjust the time limit constraint, a solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then the value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

greedy

math

sortings

*1700

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. Average Score

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputAfter 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*_{1} + *x*_{2}, where *x*_{1} is the average score in the first subject (Safety Studies), and *x*_{2} is the average score in the second one (Physical Education).

Input

The first line contains an integer *n* (2 ≤ *n* ≤ 10^{5}), *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*_{1}, *t*_{2}, ..., *t*_{n} (1 ≤ *t*_{i} ≤ 5), they are Polycarp's marks.

Output

Print the sequence of integers *f*_{1}, *f*_{2}, ..., *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*_{1}, *f*_{2}, ..., *f*_{n} is the smallest lexicographically.

The sequence *p*_{1}, *p*_{2}, ..., *p*_{n} is lexicographically less than *q*_{1}, *q*_{2}, ..., *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}.

Examples

Input

5

3 2

4 4 5 4 4

Output

1 1 2 1 2

Input

4

2 2

3 5 4 5

Output

1 1 2 2

Input

6

1 5

4 4 4 5 4 4

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.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/01/2023 05:40:12 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|