#include <bits/stdc++.h>
/*
40 points: see which pairs of ships can collide, sim those collisions (simultaneously if on same timestep)
30 points: ships will collide iff they are on the same diagonal
If a ship gets sunk, lines are updated
*/
std::map<int,std::map<int,std::pair<int,int>>> nediag,nwdiag,sediag,swdiag;//only "right-facing" ships will work
//type 1 faces forward, type -1 faces backwards
std::map<int,std::map<int,std::pair<int,int>>> horizls,vertls;//only East/South ships will work
std::map<int,std::vector<std::pair<int,int>>> collisions;// time, collisions
void setcolls(std::map<int,std::pair<int,int>>& cmap){
std::pair<int,std::pair<int,int>> lasts={0,{0,0}};
for(std::pair<int,std::pair<int,int>> ship:cmap){
if(lasts.second.second==1&&ship.second.second==-1){
collisions[(ship.first-lasts.first)/2].push_back({lasts.second.first,ship.second.first});
}
lasts=ship;
}
}
void setmap(std::map<int,std::map<int,std::pair<int,int>>>& cmap){
for(std::pair<int,std::map<int,std::pair<int,int>>> mp:cmap){
setcolls(mp.second);
}
}
void remship(std::map<int,std::pair<int,int>>& cmap,int index){//remove that ship
cmap.erase(index);
auto nextship=cmap.lower_bound(index);
if(nextship!=cmap.begin()){
auto prevship=nextship;
prevship--;//is ship to left of removed
if(prevship->second.second==1&&nextship->second.second==-1){
collisions[(nextship->first-prevship->first)/2].push_back({prevship->second.first,nextship->second.first});
}
}
}
int main(){
int n;
std::cin>>n;
std::vector<std::pair<std::pair<int,int>,char>> ships;
std::vector<int> status(n,1);
for(int i=0;i<n;i++){
int x,y;
char c;
std::cin>>x>>y;
std::cin>>c;
ships.push_back({{x,y},c});
switch(c){
case 'E':
nediag[x-y][x+y]={i,1};
sediag[x+y][x-y]={i,1};
horizls[y][x]={i,1};
break;
case 'W':
nwdiag[x+y][x-y]={i,-1};
swdiag[x-y][x+y]={i,-1};
horizls[y][x]={i,-1};
break;
case 'N':
nwdiag[x+y][x-y]={i,1};
nediag[x-y][x+y]={i,-1};
vertls[x][y]={i,-1};
break;
case 'S':
swdiag[x-y][x+y]={i,1};
sediag[x+y][x-y]={i,-1};
vertls[x][y]={i,1};
break;
}
}
setmap(nediag);
setmap(nwdiag);
setmap(sediag);
setmap(swdiag);
setmap(horizls);
setmap(vertls);
auto cstart=collisions.begin();
while(cstart!=collisions.end()){
std::vector<std::pair<int,int>> colls=cstart->second;
std::set<int> todel;
for(std::pair<int,int> coll:colls){
if(status[coll.first]==1&&status[coll.second]==1){
todel.insert(coll.first);
todel.insert(coll.second);
}
}
for(int i:todel){
int x=ships[i].first.first;
int y=ships[i].first.second;
switch(ships[i].second){
case 'E':
remship(nediag[x-y],x+y);
remship(sediag[x+y],x-y);
remship(horizls[y],x);
break;
case 'W':
remship(nwdiag[x+y],x-y);
remship(swdiag[x-y],x+y);
remship(horizls[y],x);
break;
case 'N':
remship(nwdiag[x+y],x-y);
remship(nediag[x-y],x+y);
remship(vertls[x],y);
break;
case 'S':
remship(swdiag[x-y],x+y);
remship(sediag[x+y],x-y);
remship(vertls[x],y);
break;
}
status[i]=0;
}
cstart=collisions.erase(cstart);
}
for(int i=0;i<n;i++){
if(status[i])std::cout<<i+1<<'\n';
}
}
