伯兰议会选举今天举行。投票正在火热进行中!
共有 n 个候选者,编号从 1 到 n。根据选举结果,k (1 ≤ k ≤ n) 位顶尖候选人将在议会中获得席位。
投票结束后,计算每位候选人的得票数。在结果表中,候选人按得票数排序。如果出现平局(票数相同),则按最后一次投票的时间排序。较早获得最后一票的候选人在结果表中排名较高。
因此,在结果表中,候选人按照得票数排序(票数越多,排名越高),如果两个候选人得票数相同,则按照最后投票的时间排序(最后投票越早,排名越高)。
零票候选人无法在议会中获得席位。因此,有可能少于 k 名候选人将在议会中获得席位。
在 Berland 有 m 名公民可以投票。他们每个人都会投票给某个候选人。每个公民将投票给 n 个候选人中的一位。选举中不存在“反对所有人”的选项。破坏公报或不参加选举的行为是不被接受的。因此,m 位公民中的每一位都会投票给 n 位候选人中的一位。
目前已有公民投票 (1 ≤ a ≤ m)。这是一次公开选举,因此对于每个公民来说,都知道该公民投票的候选人。正式地,第j位公民投票给了候选人gj。已投票的公民按时间顺序编号;即第 (j + 1) 位公民在第 j 位公民之后投票。
剩余的 m - a 公民将在选举结束前投票,他们每人将投票给 n 名候选人中的一名。
您的任务是为 n 个候选人中的每一个确定三个可能结果之一:
- 无论剩余 m - a 公民的选票如何,候选人都将被选入议会;
- 所有n个公民投票后,候选人有机会当选议会议员;
- 无论剩余的 m - a 公民的选票如何,候选人都没有机会当选为议会成员。
输入
第一行包含四个整数 n、k、m 和 a (1 ≤ k ≤ n ≤ 100, 1 ≤ m ≤ 100, 1 ≤ a ≤ m) — 候选人人数、议会席位数、柏林公民人数和已投票公民人数。
第二行包含整数序列 g1, g2, ..., ga (1 ≤ gj ≤ n),其中 gj 是第 j 个公民投票的候选人。已经投票的公民按照投票时间从小到大的顺序编号。
输出
打印由 n 个整数 r1, r2, ..., rn 组成的序列,其中:
- ri = 1表示无论剩余m - a公民的选票如何,第i名候选人都保证在议会中获得席位;
- ri = 2表示第i个候选人有机会在议会中获得席位,即剩余的m - a公民可以投票,使得该候选人在议会中获得席位;
- ri = 3 意味着无论剩余 m - a 公民的选票如何,第 i 个候选人都不会在议会中获得席位。
示例
输入 #1
3 1 5 4 1 2 1 3
输出 #1
1 3 3
输入 #2
3 1 5 3 1 3 1
输出 #2
2 3 2
输入 #3
3 2 5 3 1 3 1
输出 #3
1 2 2