“参加大型区域赛如果你想赢得金牌；参加小型区域赛如果你想获得 WF 的资格……”

2024 年 ICPC 区域赛将有 $n$ 支队伍参赛，编号为 $1$ 到 $n$。每支队伍可以用一个正整数表示其综合实力，用一个字符串表示其所属大学的缩写。在本题中，我们保证每所大学的缩写是唯一的，且所有队伍的综合实力各不相同。我们还假设在任何比赛中，实力更强的队伍排名总是优于实力较弱的队伍。

今年将举办 $k$ 场区域赛。对于第 $i$ 场区域赛，每所大学最多只能选派 $c_i$ 支队伍参赛。同时，每支队伍最多只能选择参加 $2$ 场区域赛。

现在，要求你计算每支队伍在最坏情况下的最小可能排名，前提是它们能最优地选择区域赛。注意，当一支队伍报名时，它并不知道其他队伍的报名策略，即使是来自同一所大学的队伍也是如此（但同一所大学在第 $i$ 场区域赛中的队伍总数仍然受到 $c_i$ 的限制，且我们总是假设当前考虑的队伍拥有优先报名权）。

请参考样例以更好地理解题目。

输入格式

第一行包含两个整数 $n, k$ ($1 \le n, k \le 10^5$)，分别表示队伍数量和区域赛数量。

第二行包含 $k$ 个整数 $c_1, \dots, c_k$ ($1 \le c_k \le 10^9$)。其中 $c_i$ 表示第 $i$ 场区域赛中每所大学允许参赛的队伍数量上限。

接下来的 $n$ 行，第 $i$ 行表示第 $i$ 支队伍的信息。第 $i$ 行包含一个整数 $w_i$ ($1 \le w_i \le 10^9$) 和一个字符串 $S_i$ ($1 \le |S_i| \le 10$)，分别由大写字母组成，代表第 $i$ 支队伍的综合实力和所属大学的缩写。

输出格式

输出 $n$ 行。

第 $i$ 行输出一个整数，表示在最坏情况下，如果队伍 $i$ 最优地选择区域赛，其能获得的最小可能排名。

样例

样例输入 1

5 3
1 2 3
100 THU
110 PKU
95 PKU
105 THU
115 PKU

样例输出 1

2
1
2
2
1

样例输入 2

5 2
2 3
100 THU
110 PKU
95 PKU
105 THU
115 PKU

样例输出 2

4
2
4
3
1