题目描述

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

今年将举行 $k$ 次区域赛。在第 $i$ 场区域赛中，每所大学可以选择不超过 $c_i$ 支队伍参加比赛。同时，每支参赛队可选择不超过 $2$ 场区域赛参加。

现在，请您计算一下，如果每支参赛队都最优化地选择了地区赛，那么在最坏的情况下，每支参赛队可能获得的最小名次。请注意，当一支队伍报名时，它并不知道其他队伍的报名策略，即使这些队伍来自同一所大学(但同一所大学参加第 $i$ 场区域赛比赛的队伍总数仍然受到 $c_i$ 的限制，而且我们总是假定当前正在考虑的队伍有优先报名权)。

输入格式：

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

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

在接下来的 $n$ 行中，每一行包含一个整数 $w_i(1\le w_i\le 10^9)$ 和一个由大写字母组成的字符串 $S_i (1\le|S_i|\le10)$ ，代表参赛队伍的综合实力和对应大学的简称。

输出格式：

输出 $n$ 行。

对于每一行，输出一个整数，代表该队在最坏情况下，如果最优参加的区域赛场次，可能获得的最好名次。

样例

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

2
1
2
2
1

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

4
2
4
3
1