//Decode解码  registration准考证  letter字母  the test site number考场编号
//the testee's number考生编号  Type Term类型 指令 specifies明确规定
//level数量,程度,级别  tie平局

//The corresponding Term will be the letter which specifies the level;
//对应的指令则给出代表指定级别的字母；

//If there is a tie of the scores, 
//output in increasing alphabetical order of their card numbers
//如果分数持平，则按卡号的字母顺序递增输出

#include<iostream>
#include<cstring>
#include<unordered_map>
#include<algorithm>
#include<vector>

using namespace std;

const int N=10010;

int n,m;
struct Person
{
    string id;
    int grade;

}p[N];

bool cmp(Person a,Person b)
{
    if(a.grade!=b.grade) return a.grade>b.grade;
        else return a.id<b.id;
}

int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++) cin>>p[i].id>>p[i].grade;

    for(int k=1;k<=m;k++)
    {
        string t,c;
        cin>>t>>c;

        printf("Case %d: %s %s\n",k,t.c_str(),c.c_str());
        if(t=="1")
        {
            vector<Person> persons;
            for(int i=0;i<n;i++)
                if(p[i].id[0]==c[0])
                    persons.push_back(p[i]);

            sort(persons.begin(),persons.end(),cmp);
            if(persons.empty()) cout<<"NA"<<endl;
            else 
                for(auto person:persons) 
                    printf("%s %d\n",person.id.c_str(),person.grade);
        }
        else if(t=="2")
        {
            int cnt=0,sum=0;
            for(int i=0;i<n;i++)
                if(p[i].id.substr(1,3)==c)
                {
                    cnt++;
                    sum+=p[i].grade;
                }
                if(!cnt) cout<<"NA"<<endl;
                else printf("%d %d\n",cnt,sum);
        }
        else
        {
            unordered_map<string,int> hash;
            for(int i=0;i<n;i++)
                if(p[i].id.substr(4,6)==c)
                    hash[p[i].id.substr(1,3)]++;

            vector<pair<int,string>> rooms;
            for(auto item:hash) rooms.push_back({-item.second,item.first}); //vector默认升序排练，加个符号就满足了，输入再加符号，回来，

            sort(rooms.begin(),rooms.end());
            if(rooms.empty()) cout<<"NA"<<endl;
            else
                for(auto room:rooms) 
                    printf("%s %d\n",room.second.c_str(),-room.first);
        }

    }
    return 0;
}