English · Original
Chinese · Translation
Formal · Original
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.
## Input
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.
## Output
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.
[samples]
今天正在举行贝兰议会的选举，投票正在全面进行！
总共有 #cf_span[n] 名候选人，编号从 #cf_span[1] 到 #cf_span[n]。根据选举结果，排名前 #cf_span[k]（#cf_span[1 ≤ k ≤ n]）的候选人将获得议会席位。
投票结束后，将计算每位候选人的得票数。在最终的排名表中，候选人按得票数排序。若出现平票（得票数相同），则按最后一次投票的时间排序：最后一次投票时间更早的候选人排名更高。
因此，最终排名表中候选人按得票数降序排列（得票越多排名越高）；若得票数相同，则按最后一次投票时间升序排列（最后一次投票时间越早排名越高）。
得票为零的候选人无法获得议会席位。因此，实际获得席位的候选人数量可能少于 #cf_span[k]。
在贝兰，有 #cf_span[m] 名公民有权投票。每人将投票给其中一名候选人。每位公民必须投票给 #cf_span[n] 名候选人中的恰好一人。选举中没有“反对所有人”的选项，也不允许投废票或不参加选举。因此，#cf_span[m] 名公民每人将投票给 #cf_span[n] 名候选人中的恰好一人。
目前已有 #cf_span[a] 名公民投过票（#cf_span[1 ≤ a ≤ m]）。由于这是公开选举，因此已知每位已投票公民所投的候选人。形式上，第 #cf_span[j] 名公民投票给了候选人 #cf_span[gj]。已投票的公民按投票时间顺序编号；即第 #cf_span[(j + 1)] 名公民在第 #cf_span[j] 名公民之后投票。
剩余的 #cf_span[m - a] 名公民将在选举结束前投票，每人将投票给 #cf_span[n] 名候选人中的其中一人。
你的任务是为每位 #cf_span[n] 名候选人确定以下三种可能结果之一：
第一行包含四个整数 #cf_span[n], #cf_span[k], #cf_span[m] 和 #cf_span[a]（#cf_span[1 ≤ k ≤ n ≤ 100]，#cf_span[1 ≤ m ≤ 100]，#cf_span[1 ≤ a ≤ m]）——分别表示候选人数量、议会席位数量、贝兰公民总数和已投票公民数量。
第二行包含一个长度为 #cf_span[a] 的整数序列 #cf_span[g1, g2, ..., ga]（#cf_span[1 ≤ gj ≤ n]），其中 #cf_span[gj] 表示第 #cf_span[j] 名已投票公民所投的候选人。已投票公民按投票时间递增顺序编号。
## Input
第一行包含四个整数 #cf_span[n], #cf_span[k], #cf_span[m] 和 #cf_span[a]（#cf_span[1 ≤ k ≤ n ≤ 100]，#cf_span[1 ≤ m ≤ 100]，#cf_span[1 ≤ a ≤ m]）——分别表示候选人数量、议会席位数量、贝兰公民总数和已投票公民数量。第二行包含一个长度为 #cf_span[a] 的整数序列 #cf_span[g1, g2, ..., ga]（#cf_span[1 ≤ gj ≤ n]），其中 #cf_span[gj] 表示第 #cf_span[j] 名已投票公民所投的候选人。已投票公民按投票时间递增顺序编号。
## Output
请输出一个包含 #cf_span[n] 个整数的序列 #cf_span[r1, r2, ..., rn]，其中：
#cf_span[ri = 1] 表示无论剩余 #cf_span[m - a] 名公民如何投票，第 #cf_span[i] 名候选人都能确保获得议会席位；
#cf_span[ri = 2] 表示第 #cf_span[i] 名候选人有机会获得议会席位，即剩余 #cf_span[m - a] 名公民可以以某种方式投票，使该候选人获得席位；
#cf_span[ri = 3] 表示无论剩余 #cf_span[m - a] 名公民如何投票，第 #cf_span[i] 名候选人都无法获得议会席位。
[samples]
**Definitions**
Let $ n, k, m, a \in \mathbb{Z}^+ $ with $ 1 \leq k \leq n \leq 100 $, $ 1 \leq a \leq m \leq 100 $.
Let $ G = (g_1, g_2, \dots, g_a) $ be the sequence of votes from the first $ a $ citizens, where $ g_j \in \{1, \dots, n\} $ is the candidate voted for by the $ j $-th voter.
Let $ V_i \in \mathbb{N} $ denote the current number of votes for candidate $ i \in \{1, \dots, n\} $, initialized from $ G $.
Let $ T_i \in \mathbb{N} $ denote the timestamp (i.e., the index) of the last vote for candidate $ i $, or $ 0 $ if no vote yet; initialized from $ G $.
Let $ r = m - a $ be the number of remaining voters, each of whom will vote for exactly one candidate in $ \{1, \dots, n\} $.
**Constraints**
1. $ V_i \geq 0 $, $ T_i \in \{0, 1, \dots, a\} $ for all $ i \in \{1, \dots, n\} $.
2. Each of the $ r $ remaining votes can be assigned arbitrarily to any candidate $ i \in \{1, \dots, n\} $.
3. A candidate with $ V_i = 0 $ cannot win a seat.
**Objective**
For each candidate $ i \in \{1, \dots, n\} $, determine the outcome $ r_i \in \{\text{WIN}, \text{LOSE}, \text{MAYBE}\} $, where:
- $ r_i = \text{WIN} $ if candidate $ i $ is guaranteed to be among the top $ k $ non-zero-vote candidates under *all* possible assignments of the remaining $ r $ votes.
- $ r_i = \text{LOSE} $ if candidate $ i $ cannot be among the top $ k $ non-zero-vote candidates under *any* assignment of the remaining $ r $ votes.
- $ r_i = \text{MAYBE} $ otherwise.
Candidates are ranked by:
1. **Primary**: descending number of total votes $ V_i $.
2. **Secondary**: ascending timestamp of last vote $ T_i $ (earlier is better).
The top $ \min(k, \text{number of candidates with } V_i > 0) $ candidates win seats.
API Response (JSON)
{
"problem": {
"name": "F. Berland Elections",
"description": {
"content": "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 ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF847F"
},
"statements": [
{
"statement_type": "Markdown",
"content": "The elections to Berland parliament are happening today. Voting is in full swing!\n\nTotally there are _n_ candidates, they are numbered from 1 to _n_. Based on election results _k_ (1 ≤ _k_ ≤ _n_) top ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "今天正在举行贝兰议会的选举，投票正在全面进行！\n\n总共有 #cf_span[n] 名候选人，编号从 #cf_span[1] 到 #cf_span[n]。根据选举结果，排名前 #cf_span[k]（#cf_span[1 ≤ k ≤ n]）的候选人将获得议会席位。\n\n投票结束后，将计算每位候选人的得票数。在最终的排名表中，候选人按得票数排序。若出现平票（得票数相同），则按最后一次投票的时间排序：最后...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, k, m, a \\in \\mathbb{Z}^+ $ with $ 1 \\leq k \\leq n \\leq 100 $, $ 1 \\leq a \\leq m \\leq 100 $. \nLet $ G = (g_1, g_2, \\dots, g_a) $ be the sequence of votes from the first $ a ...",
"is_translate": false,
"language": "Formal"
}
]
}