#include<iostream>
#include<vector>
#include<map>
#include<unordered_map>
#include<algorithm>
using namespace std;
struct ss {
	string xuehao;
	string jibie;
	string gcnum;
	string date;
	string snum;
	int score;
} ans[10003];
int n,m;
bool cmp1(pair<string,int>& a,pair<string ,int>& b) {
	return a.second==b.second?a.first<b.first:a.second>b.second;
}
unordered_map<string,vector<pair<string,int>>> ans11;
void f1() {
	string t="ABT";
	for(int j=0; j<3; ++j) {
		string jibie=t.substr(j,1);
		unordered_map<string ,int> s;
		for(int i=0; i<n; ++i)
			if(ans[i].jibie==jibie)
				s[ans[i].xuehao]=ans[i].score;
		vector<pair<string,int>> ans1(s.begin(),s.end());
		sort(ans1.begin(),ans1.end(),cmp1);
		ans11[jibie]=ans1;
	}
}
unordered_map<string ,pair<int,int>>ans22;
void f2() {
	for(int j=101; j<=999; ++j) {
		string gcnum=to_string(j);
		int num=0,score=0;
		for(int i=0; i<n; ++i)
			if(ans[i].gcnum==gcnum) {
				num++;
				score+=ans[i].score;
			}
		ans22[gcnum]=make_pair(num,score);
	}
}
unordered_map<string,vector<pair<string,int>>> ans33;
void f3(int k) {
	string date;
	cin>>date;
	printf("Case %d: 3 %s\n",k,date.c_str());
	if(ans33[date].size()) {
		for(auto it=ans33[date].begin(); it!=ans33[date].end(); ++it)
			printf("%s %d\n",(*it).first.c_str(),(*it).second);
	} else {
		unordered_map<string,int> s;
		for(int i=0; i<n; ++i)
			if(ans[i].date==date)
				s[ans[i].gcnum]++;
		if(!s.size())
			printf("NA\n");
		else {
			vector<pair<string,int>> ans1(s.begin(),s.end());
			sort(ans1.begin(),ans1.end(),cmp1);
			for(auto it=ans1.begin(); it!=ans1.end(); ++it)
				printf("%s %d\n",(*it).first.c_str(),(*it).second);
			ans33[date]=ans1;
		}
	}
}
int main() {
	cin>>n>>m;
	for(int i=0; i<n; ++i) {
		string s;
		int score;
		cin>>s>>score;
		ans[i].xuehao=s;
		ans[i].score=score;
		ans[i].jibie=s.substr(0,1);
		ans[i].gcnum=s.substr(1,3);
		ans[i].date=s.substr(4,6);
		ans[i].snum=s.substr(10,4);
	}
	f1();//对于前两种指令可以先跑出来结果存着 
	f2();
	for(int i=0; i<m; ++i) {
		int c;
		cin>>c;
		switch(c) {
			case 1: {
				string jibie;
				cin>>jibie;
				printf("Case %d: 1 %s\n",i+1,jibie.c_str());
				if(!ans11[jibie].size())
					printf("NA\n");
				else
					for(auto it=ans11[jibie].begin(); it!=ans11[jibie].end(); ++it)
						printf("%s %d\n",(*it).first.c_str(),(*it).second);

				break;
			}
			case 2: {
				string gcnum;
				cin>>gcnum;
				printf("Case %d: 2 %s\n",i+1,gcnum.c_str());
				if(!ans22[gcnum].first)
					printf("NA\n");
				else printf("%d %d\n",ans22[gcnum].first,ans22[gcnum].second);
				break;
			}
			case 3:
				f3(i+1);//现跑，边跑边记录 
				break;
		}
	}
	return 0;
}