#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAX_BAT=200*1000+5,INFINI=1000*1000*1000+5;
int nbBat;
pair<int,int> coord[MAX_BAT];
int direc[MAX_BAT],dateInter[MAX_BAT];
vector<tuple<int,int,int>> intersect;
vector<pair<int,int>> corres;
int calcInter(int bat1,int bat2) {
int dist=0;
if (coord[bat1].first==coord[bat2].first) {
dist=abs(coord[bat1].second-coord[bat2].second)/2;
}
else if (coord[bat1].second==coord[bat2].second) {
dist=abs(coord[bat1].first-coord[bat2].first)/2;
}
else if (abs(coord[bat1].first-coord[bat2].first)==abs(coord[bat1].second-coord[bat2].second)) {
dist=abs(coord[bat1].first-coord[bat2].first);
}
else {
return INFINI;
}
if (coord[bat1].first+dist*corres[direc[bat1]].first==coord[bat2].first+dist*corres[direc[bat2]].first and
coord[bat1].second+dist*corres[direc[bat1]].second==coord[bat2].second+dist*corres[direc[bat2]].second) {
return dist;
}
return INFINI;
}
void calc(vector<int> numBat) {
int taille=numBat.size();
set<pair<int,int>> posBat;
for (int i:numBat) {
posBat.insert({coord[i].first,i});
}
priority_queue<pair<int,int>> possi;
auto it=posBat.begin();
int bat1,bat2,batSup;
for (int i=0;i<taille-1;i++) {
bat1=(*it).second;
it++;
bat2=(*it).second;
if (direc[bat1]==1 and direc[bat2]==2) {
possi.push({-(coord[bat2].first-coord[bat1].first),bat1});
}
}
while (!possi.empty()) {
batSup=possi.top().second;
possi.pop();
it=posBat.lower_bound({coord[batSup].first,batSup});
posBat.erase(it);
it=posBat.lower_bound({coord[batSup].first,batSup});
posBat.erase(it);
it=posBat.lower_bound({coord[batSup].first,batSup});
if (it!=posBat.end()) {
bat2=(*it).second;
if (it!=posBat.begin()) {
it--;
bat1=(*it).second;
if (direc[bat1]==1 and direc[bat2]==2) {
possi.push({-(coord[bat2].first-coord[bat1].first),bat1});
}
}
}
}
for (auto i:posBat) {
cout<<i.second<<"\n";
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
corres={{0,-1},{1,0},{0,1},{-1,0}};
cin>>nbBat;
char carac;
vector<pair<int,int>> diagTri;
for (int i=1;i<=nbBat;i++) {
cin>>coord[i].first>>coord[i].second>>carac;
if (carac=='N') {
direc[i]=0;
}
if (carac=='E') {
direc[i]=1;
}
if (carac=='S') {
direc[i]=2;
}
if (carac=='W') {
direc[i]=3;
}
diagTri.push_back({coord[i].first+coord[i].second,i});
}
sort(diagTri.begin(),diagTri.end());
vector<int> enCours;
int dern=-1;
for (auto i:diagTri) {
if (dern==i.first) {
enCours.push_back(i.second);
}
else {
calc(enCours);
enCours.clear();
enCours.push_back(i.second);
dern=i.first;
}
}
calc(enCours);
return 0;
}
