A. Gambling on Choosing Regionals
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

"Participate in large regionals if you want to win gold medals; participate in small regionals if you want to get the qualify to WF..."

There will be $$$n$$$ teams participating in the 2024 ICPC Regional Contests numbered from $$$1$$$ to $$$n$$$. Each team can be described by a positive integer represents its comprehensive strength and a string represents the abbreviation of the university it belongs to. In this problem, we guarantee that the abbreviation of each university is unique and the comprehensive strengths of the teams are pairwise distinct. We also assume that the stronger team will always be ranked ahead of the weaker team in any contest.

This year, $$$k$$$ regional contests will be held. For the $$$i$$$-th regional contest, every university can select no more than $$$c_i$$$ teams to join the contest. Meanwhile, each team can select no more than $$$2$$$ regional contests to participate in.

Now, you are asked to calculate the smallest possible rank for each team in the worst case, if they choose the regionals optimally. Note that when a team registers, it does not know the registration strategy of other teams, even if they are from the same university (but the total number of teams in the same university for the $$$i$$$-th regional contest is still limited by the $$$c_i$$$, and we always assume that the team currently under consideration has priority to register).

Please refer to the samples to understand the problem better.

Input

The first line contains two integers $$$n,k\ (1\le n, k\le 10^5)$$$, representing the number of teams and the number of regional contests.

The second line contains $$$k$$$ integers $$$c_1, \cdots, c_k\ (1\le c_k\le 10^9)$$$. Where $$$c_i$$$ indicates the limit on the number of teams from every university in the $$$i$$$-th regional contest.

For the following $$$n$$$ lines, the $$$i$$$-th line indicates the information of the team $$$i$$$. the $$$i$$$-th line contains an integer $$$w_i\ (1\le w_i\le 10^9)$$$ and a string $$$S_i\ (1\le|S_i|\le10)$$$ consisting of uppercase letters, representing the comprehensive strength and the abbreviation of the corresponding university of the team $$$i$$$.

Output

Output $$$n$$$ lines.

For the $$$i$$$-th line, print a single integer representing the smallest possible rank for the team $$$i$$$ in the worst case, if they choose the regionals optimally.

Examples
Input
5 3
1 2 3
100 THU
110 PKU
95 PKU
105 THU
115 PKU
Output
2
1
2
2
1
Input
5 2
2 3
100 THU
110 PKU
95 PKU
105 THU
115 PKU
Output
4
2
4
3
1