CF847F.Berland Elections

The elections to Berland parliament are happening today. Voting is in full swing!

Totally there are n candidates, they are numbered from 1 to n. Based on election results k (1 ≤ k ≤ n) top candidates will take seats in the parliament.

After the end of the voting the number of votes for each candidate is calculated. In the resulting table the candidates are ordered by the number of votes. In case of tie (equal number of votes) they are ordered by the time of the last vote given. The candidate with ealier last vote stands higher in the resulting table.

So in the resulting table candidates are sorted by the number of votes (more votes stand for the higher place) and if two candidates have equal number of votes they are sorted by the time of last vote (earlier last vote stands for the higher place).

There is no way for a candidate with zero votes to take a seat in the parliament. So it is possible that less than k candidates will take a seat in the parliament.

In Berland there are m citizens who can vote. Each of them will vote for some candidate. Each citizen will give a vote to exactly one of n candidates. There is no option "against everyone" on the elections. It is not accepted to spoil bulletins or not to go to elections. So each of m citizens will vote for exactly one of n candidates.

At the moment a citizens have voted already (1 ≤ a ≤ m). This is an open election, so for each citizen it is known the candidate for which the citizen has voted. Formally, the j-th citizen voted for the candidate g__j. The citizens who already voted are numbered in chronological order; i.e. the (j + 1)-th citizen voted after the j-th.

The remaining m - a citizens will vote before the end of elections, each of them will vote for one of n candidates.

Your task is to determine for each of n candidates one of the three possible outcomes:

• a candidate will be elected to the parliament regardless of votes of the remaining m - a citizens;
• a candidate has chance to be elected to the parliament after all n citizens have voted;
• a candidate has no chances to be elected to the parliament regardless of votes of the remaining m - a citizens.

今天正在举行贝尔兰议会选举，投票工作正在如火如荼地进行！

总共有 $n$ 名候选人，编号为 $1$ 至 $n$。根据选举结果，得票数排名前 $k$（$1 \leq k \leq n$）的候选人将获得议会席位。

投票结束后，将统计每位候选人的得票数。在最终的排名表中，候选人按得票数从高到低排序；若得票数相同，则按其最后一票的投票时间先后排序：最后一票时间更早者排名更高。

因此，在最终排名表中，候选人首先按得票数降序排列（得票数越多，名次越高）；若得票数相等，则按最后一票时间升序排列（最后一票时间越早，名次越高）。

得票数为 $0$ 的候选人不可能获得议会席位。因此，实际进入议会的候选人人数可能少于 $k$ 人。

贝尔兰共有 $m$ 名具有投票权的公民，每人将投出一票。每位公民将恰好为 $n$ 名候选人中的某一位投票。本次选举中没有“反对所有候选人”选项；选票作废或弃权均不被允许。因此，全部 $m$ 名公民都将恰好为 $n$ 名候选人中的某一位投票。

截至目前，已有 $a$ 名公民完成投票（$1 \leq a \leq m$）。本次选举为公开选举，因此对每位已投票公民，均已知其所投的候选人。形式化地，第 $j$ 位公民投给了候选人 $g_j$。已投票的公民按时间顺序编号，即第 $(j+1)$ 位公民在第 $j$ 位公民之后投票。

剩余的 $m - a$ 名公民将在选举结束前完成投票，每人将为 $n$ 名候选人中的某一位投票。

你的任务是：对每位候选人（共 $n$ 位），判断以下三种情况之一：

• 该候选人必定当选议会——无论剩余 $m - a$ 名公民如何投票；
• 该候选人有可能当选议会——存在某种剩余 $m - a$ 名公民的投票方式，使其最终当选；
• 该候选人绝无可能当选议会——无论剩余 $m - a$ 名公民如何投票，其均无法当选。

The first line contains four integers n, k, m and a (1 ≤ k ≤ n ≤ 100, 1 ≤ m ≤ 100, 1 ≤ a ≤ m) — the number of candidates, the number of seats in the parliament, the number of Berland citizens and the number of citizens who already have voted.

The second line contains a sequence of a integers _g_1, _g_2, ..., g__a (1 ≤ g__j ≤ n), where g__j is the candidate for which the j-th citizen has voted. Citizens who already voted are numbered in increasing order of voting times.

第一行包含四个整数 $n$、$k$、$m$ 和 $a$（$1 \le k \le n \le 100$，$1 \le m \le 100$，$1 \le a \le m$）—— 分别表示候选人数量、议会席位数、Berland 国公民总数以及已投票的公民人数。

第二行包含一个由 $a$ 个整数构成的序列 $g_1,\,g_2,\,...,\,g_a$（$1 \le g_j \le n$），其中 $g_j$ 表示第 $j$ 位公民所投的候选人编号。已投票的公民按投票时间先后顺序依次编号（即编号递增）。

Print the sequence consisting of n integers _r_1, _r_2, ..., r__n where:

• r__i = 1 means that the i-th candidate is guaranteed to take seat in the parliament regardless of votes of the remaining m - a citizens;
• r__i = 2 means that the i-th candidate has a chance to take a seat in the parliament, i.e. the remaining m - a citizens can vote in such a way that the candidate will take a seat in the parliament;
• r__i = 3 means that the i-th candidate will not take a seat in the parliament regardless of votes of the remaining m - a citizens.

输出由 $n$ 个整数 $r_1,\ r_2,\ \dots,\ r_n$ 构成的序列，其中：

• $r_i = 1$ 表示第 $i$ 位候选人必定能进入议会就座，无论其余 $m - a$ 名公民如何投票；
• $r_i = 2$ 表示第 $i$ 位候选人有可能进入议会就座，即存在一种其余 $m - a$ 名公民的投票方式，使得该候选人能够进入议会就座；
• $r_i = 3$ 表示第 $i$ 位候选人必定无法进入议会就座，无论其余 $m - a$ 名公民如何投票。