← 返回题目列表

Codeforces · 81/C

C. 平均分

中文机器翻译题面 查看原题

教育改革后,波利卡普在学校只学习两门科目:安全学和体育(体育)。在第四个学期漫长的几个月里,他获得了 n 分。当老师在日记中写分数时,他们没有写分数是针对哪个科目的,他们只是写了分数。

现在是时候向他严格的父母展示日记了。 Polycarp 知道,最近在家长会上,家长被告知他获得了安全研究分数和 b PE 分数(a + b = n)。现在波利卡普想在每个标记前面写上一个主题的名字,这样:

- 有一个安全研究标记,
- 正好有 b 个 PE 标记,
- 两门科目的总平均分最高。

平均学科成绩是其中所有分数的总和除以分数的数量。当然,除法是按实数进行的,不进行向上或向下舍入。 Polycarp 的目标是最大化 x1 + x2,其中 x1 是第一科目(安全研究)的平均分数,x2 是第二科目(体育)的平均分数。

输入

第一行包含一个整数n (2 ≤ n ≤ 105),n 是Polycarp 日记中的标记数。第二行包含两个正整数a、b (1 ≤ a, b ≤ n - 1, a + b = n)。第三行包含整数序列 t1, t2, ..., tn (1 ≤ ti ≤ 5),它们是波利卡普的标记。

输出

打印整数序列 f1, f2, ..., fn,其中 fi (1 ≤ fi ≤ 2) 是第 i 个标记应归属的主题编号。如果有多个可能的解决方案,则打印使得序列 f1, f2, ..., fn 按字典顺序最小。

如果存在 j (1 ≤ j ≤ n),对于所有 1 ≤ i < j 且 pj < qj,pi = qi,则序列 p1, p2, ..., pn 按字典顺序小于 q1, q2, ..., qn。

示例

输入 #1

5
3 2
4 4 5 4 4

输出 #1

1 1 2 1 2

输入 #2

4
2 2
3 5 4 5

输出 #2

1 1 2 2

输入 #3

6
1 5
4 4 4 5 4 4

输出 #3

2 2 2 1 2 2

注意

在第一个样本中,第一个科目的平均分数等于 4,第二个科目的平均分数等于 4.5。总平均分是8.5分。