#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;

    vector<int> c(k);
    for (int i = 0; i < k; i++) {
        cin >> c[i]; // limits of teams per university for each contest
    }

    vector<pair<int, string>> teams(n);
    for (int i = 0; i < n; i++) {
        cin >> teams[i].first >> teams[i].second; // strength and university abbreviation
    }

    // Sort teams by strength in descending order
    sort(teams.begin(), teams.end(), greater<pair<int, string>>());

    // Map to keep track of university registrations
    map<string, vector<int>> university_teams;
    for (const auto& team : teams) {
        university_teams[team.second].push_back(team.first);
    }

    // Result array for ranks
    vector<int> ranks(n);
    
    // Process each team to calculate the worst-case rank
    for (int i = 0; i < n; i++) {
        int current_strength = teams[i].first;
        string current_university = teams[i].second;
        
        int worst_rank = i + 1; // Initial worst rank is its current position

        // Check all contests
        for (int contest = 0; contest < k; contest++) {
            int max_teams = c[contest];
            int count_stronger = 0;

            // Count how many stronger teams would be in this contest
            for (int j = 0; j < n; j++) {
                if (teams[j].second == current_university) continue; // Skip teams from the same university
                if (teams[j].first > current_strength) {
                    count_stronger++;
                }
            }

            // Calculate potential worst rank considering this contest's limit
            if (count_stronger < max_teams) {
                // We can take some teams from this university
                int available_spots = max_teams - count_stronger;
                int teams_from_university = min(available_spots, (int)university_teams[current_university].size());

                worst_rank = min(worst_rank, count_stronger + teams_from_university + 1);
            }
        }

        // Store the calculated worst rank
        ranks[i] = worst_rank;
    }

    // Output the ranks
    for (int i = 0; i < n; i++) {
        cout << ranks[i] << endl;
    }

    return 0;
}