#include<set>
#include<unordered_map>
#define REP(i,x,n) for(int i= (int)(x); i<(int)(n);++i)
#define MP make_pair
using namespace std;
struct student{
int id;
int grade;
int gender;
int score;
};
struct compare{
bool operator()(pair<int,int> a,pair<int,int> b){
if(a.first!=b.first)
return a.first<b.first;
return a.second<b.second;
}
};
student student_list[20001];
int idx;
unordered_map<int,int> hashtable;
set<pair<int,int>,compare> Score[4][2];
void init(){
idx=0;
hashtable.clear();
for(int i=1;i<=3;i++)
{
for(int j=0;j<=1;j++)
Score[i][j].clear();
}
}
int add(int mId,int mGrade,char mGender[7],int mScore){
int gender = (mGender[0]=='m')?0:1;
student_list[++idx].id=mId;
student_list[idx].grade = mGrade;
student_list[idx].gender = gender;
student_list[idx].score = mScore;
hashtable[mId]=idx;
Score[mGrade][gender].insert(make_pair(mScore,mId));
return Score[mGrade][gender].rbegin()->second;
}
int remove(int mId)
{
if(hashtable.find(mId)==hashtable.end())
return 0;
hashtable.erase(mId);
int grade = student_list[hashtable[mId]].grade;
int gender = student_list[hashtable[mId]].gender;
int score = student_list[hashtable[mId]].score;
Score[grade][gender].erase(make_pair(score,mId));
if(Score[grade][gender].empty())
return 0;
else
return Score[grade][gender].begin()->second;
}
int query(int mGradeCnt,int mGrade[],int mGenderCnt,char mGender[][7],int mScore)
{
int res=1e9+7;
int id = 1e9+7;
bool flag=0;
for(int i=0;i<mGradeCnt;i++)
{
for(int j=0;j<mGenderCnt;j++)
{
int grade = mGrade[i];
int gender = mGender[j][0]=='l';
auto it = Score[grade][gender].lower_bound(make_pair(mScore,-1));
if(it==Score[grade][gender].end())
continue;
if(it->first<res || (it->first==res && it->second<id)){
res=it->first;
id = it->second;
flag=1;
}
}
}
if(flag)
return id;
return 0;
}