#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e5+10;
struct node
{
	int num;
};
node tree[4*maxn];
int c[maxn],id,res = 1e9+10,a[maxn],b[maxn];
string s[maxn];
map<string,int> mp;
map<int,int> mp1;
vector<int>v[maxn];
int ans[maxn],last[maxn];
bool vis[maxn];


void pushup(int root)
{
	tree[root].num = tree[root<<1].num + tree[root<<1|1].num;
}
void update(int root,int l,int r,int x,int k)
{
	if(l == r)
	{
		tree[root].num += k;
		return;
	}
	int mid = (l+r) >> 1;
	if(x <= mid)	update(root<<1,l,mid,x,k);
	else	update(root<<1|1,mid+1,r,x,k);
	pushup(root);
}

int query(int root,int l,int r,int x)
{
	if(l == r)
		return 1;
	int mid = (l+r) >> 1;
	if(x <= mid)	return query(root<<1,l,mid,x) + tree[root<<1|1].num;
	else	return query(root<<1|1,mid+1,r,x);
}
int main()
{
	int n,k;
	scanf("%d%d",&n,&k);
	for(int i = 1;i <= k;i++)
		scanf("%d",&c[i]),res = min(res,c[i]);
	for(int i = 1;i <= n;i++)
	{
		int	x;
		cin >> x >> s[i];
		if(mp.find(s[i]) == mp.end())
			mp[s[i]] = ++id;
		v[mp[s[i]]].push_back(x);
		a[i] = x;
		b[i] = x;
	} 
	sort(a+1,a+n+1);
	for(int i = 1;i <= id;i++)
	{
		sort(v[i].begin(),v[i].end(),greater<int>());
		int len = v[i].size();
		int j;
		for(j = 0;j < min(res,len);j++)
		{
			int x = lower_bound(a+1,a+n+1,v[i][j]) - a;
			update(1,1,n,x,1);
			vis[v[i][j]] = 1;
		}
		last[i] = v[i][j-1];
	}
	for(int i = 1;i <= n;i++)
	{
		if(vis[b[i]])	
		{
		//	cout << "------" << b[i] << endl;
			int x = lower_bound(a+1,a+n+1,b[i]) - a;
			printf("%d\n",query(1,1,n,x));
		}
		else
		{
			int id1 = lower_bound(a+1,a+n+1,last[mp[s[i]]]) - a;
			int id2 = lower_bound(a+1,a+n+1,b[i]) - a;
			update(1,1,n,id1,-1);
			update(1,1,n,id2,1);
			printf("%d\n",query(1,1,n,id2));
			update(1,1,n,id1,1);
			update(1,1,n,id2,-1);
		}
	}
	return 0;
}