#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include<queue>
#include<map>
#include<set>
#define int long long
using namespace std;
const int N=5e3+10;
const int M=1e4+10;



struct node
{
    int srank;
    string name;
    int pos;
}a[N];

int c[N];
map<string,int>ma;

int d[N];//用于记录每个队伍最终可以达到的最好情况下的最差成绩

bool cmp(node a1,node a2)
{
    return a1.srank>a2.srank;
}

void solve()
{
    int n,k;cin>>n>>k;
    ma.clear();
    for(int i=1;i<=k;i++) cin>>c[i];

    sort(c+1,c+1+k);
    for(int i=1;i<=n;i++){
        cin>>a[i].srank>>a[i].name;
        a[i].pos=i;
    }

    sort(a+1,a+1+n,cmp);
    memset(d,0x3f,sizeof(d));
    int m=0;
    for(int i=1;i<=n;i++){
        if(ma[a[i].name]<c[1]){
            d[a[i].pos]=min(i-m,d[a[i].pos]);
            ma[a[i].name]++;
        }
        else{
            m++;
            d[a[i].pos]=min(i-m,d[a[i].pos]);
            ma[a[i].name]++;
        }
    }
    for(int i=1;i<=n;i++){
        cout<<d[i]<<endl;
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    /*int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }*/

    solve();
    return 0;
}