#include <bits/stdc++.h>
using namespace std;
using pii=pair<int, int>;
priority_queue<array<int, 6>, vector<array<int, 6>>, greater<array<int, 6>>> pq;
vector<int> X, Y;
struct nodo{
int ind, l, r;
bool aperta;
nodo(int i, int left, bool a){
ind=i, l=left, aperta=a, r=-1;
}
};
void pop(vector<nodo> &v, int ind, int diagType, int diagInd){
if(v[ind].l==-1 && v[ind].r==-1){
return;
}else if(v[ind].l==-1){
int nextNodeInd=v[ind].r;
v[nextNodeInd].l=-1;
return;
}else if(v[ind].r==-1){
int prevNodeInd=v[ind].l;
v[prevNodeInd].r=-1;
return;
}else{
int prevNodeInd=v[ind].l, nextNodeInd=v[ind].r;
v[prevNodeInd].r=nextNodeInd;
v[nextNodeInd].l=prevNodeInd;
if(v[prevNodeInd].aperta && !v[nextNodeInd].aperta){
array<int, 6> scontro;
int i1=v[prevNodeInd].ind, i2=v[nextNodeInd].ind;
int time;
if(diagType<4) time=abs(X[i2]-X[i1]); //abs non servirebbe ma better safe than sorry
else if(diagType==4) time=abs(X[i2]-X[i1])/2;
else if(diagType==5) time=abs(Y[i2]-Y[i1])/2;
scontro={time, i1, i2, diagType, diagInd, prevNodeInd};
pq.push(scontro);
}
}
}
void pop2(vector<nodo> &v, int ind1, int ind2, int diagType, int diagInd){
if(v[ind1].l==-1 && v[ind2].r==-1){
return;
}else if(v[ind1].l==-1){
int nextNodeInd=v[ind2].r;
v[nextNodeInd].l=-1;
return;
}else if(v[ind2].r==-1){
int prevNodeInd=v[ind1].l;
v[prevNodeInd].r=-1;
return;
}else{
int prevNodeInd=v[ind1].l, nextNodeInd=v[ind2].r;
v[prevNodeInd].r=nextNodeInd;
v[nextNodeInd].l=prevNodeInd;
if(v[prevNodeInd].aperta && !v[nextNodeInd].aperta){
array<int, 6> scontro;
int i1=v[prevNodeInd].ind, i2=v[nextNodeInd].ind;
int time;
if(diagType<4) time=abs(X[i2]-X[i1]); //abs non servirebbe ma better safe than sorry
else if(diagType==4) time=abs(X[i2]-X[i1])/2;
else if(diagType==5) time=abs(Y[i2]-Y[i1])/2;
scontro={time, i1, i2, diagType, diagInd, prevNodeInd};
pq.push(scontro);
}
}
}
int findDiagInd(int diagType, int x, int y){
if(diagType==0 || diagType==3) return x+y;
if(diagType==1 || diagType==2) return x-y;
if(diagType==4) return y;
if(diagType==5) return x;
}
vector<int> affonda(int N, vector<char> D){
vector<array<int, 4>> navi(N);
vector<bool> isAlive(N, true);
for(int i=0; i<N; i++) navi[i]={X[i], Y[i], D[i], i};
sort(navi.begin(), navi.end());
vector<map<int, vector<nodo>>> diagonali(6);
/* 0 -> SE
1 -> SW
2 -> NE
3 -> NW
4 -> horizontal
5 -> vertical*/
for(int i=0; i<N; i++){
int xAtt=navi[i][0], yAtt=navi[i][1], dAtt=navi[i][2], indAtt=navi[i][3];
if(dAtt=='S'){
vector<int> possibleDiagonals={0, 1, 5}; //SE, SW, vertical
for(int diagAtt : possibleDiagonals){
bool aperta=true;
if(diagAtt==0) aperta=false;
int diagInd=findDiagInd(diagAtt, xAtt, yAtt);
if(!diagonali[diagAtt][diagInd].empty())
diagonali[diagAtt][diagInd][diagonali[diagAtt][diagInd].size()-1].r=diagonali[diagAtt][diagInd].size();
diagonali[diagAtt][diagInd].push_back(nodo(indAtt, diagonali[diagAtt][diagInd].size()-1, aperta));
}
}if(dAtt=='E'){
vector<int> possibleDiagonals={0, 2, 4}; //SE, NE, horizontal
for(int diagAtt : possibleDiagonals){
bool aperta=true;
int diagInd=findDiagInd(diagAtt, xAtt, yAtt);
if(!diagonali[diagAtt][diagInd].empty())
diagonali[diagAtt][diagInd][diagonali[diagAtt][diagInd].size()-1].r=diagonali[diagAtt][diagInd].size();
diagonali[diagAtt][diagInd].push_back(nodo(indAtt, diagonali[diagAtt][diagInd].size()-1, aperta));
}
}if(dAtt=='N'){
vector<int> possibleDiagonals={2, 3, 5}; //NE, NW, vertical
for(int diagAtt : possibleDiagonals){
bool aperta=false;
if(diagAtt==3) aperta=true;
int diagInd=findDiagInd(diagAtt, xAtt, yAtt);
if(!diagonali[diagAtt][diagInd].empty())
diagonali[diagAtt][diagInd][diagonali[diagAtt][diagInd].size()-1].r=diagonali[diagAtt][diagInd].size();
diagonali[diagAtt][diagInd].push_back(nodo(indAtt, diagonali[diagAtt][diagInd].size()-1, aperta));
}
}if(dAtt=='W'){
vector<int> possibleDiagonals={1, 3, 4}; //SW, NW, horizontal
for(int diagAtt : possibleDiagonals){
bool aperta=false;
int diagInd=findDiagInd(diagAtt, xAtt, yAtt);
if(!diagonali[diagAtt][diagInd].empty())
diagonali[diagAtt][diagInd][diagonali[diagAtt][diagInd].size()-1].r=diagonali[diagAtt][diagInd].size();
diagonali[diagAtt][diagInd].push_back(nodo(indAtt, diagonali[diagAtt][diagInd].size()-1, aperta));
}
}
}
for(int diagAtt=0; diagAtt<6; diagAtt++){
for(auto const& p : diagonali[diagAtt]){
vector<nodo> currDiag=p.second;
for(int i=1; i<currDiag.size(); i++){
if(currDiag[i-1].aperta && !currDiag[i].aperta){
array<int, 6> scontro;
int i1=currDiag[i-1].ind, i2=currDiag[i].ind;
int time;
if(diagAtt<4) time=abs(X[i2]-X[i1]); //abs non servirebbe ma better safe than sorry
else if(diagAtt==4) time=abs(X[i2]-X[i1])/2;
else if(diagAtt==5) time=abs(Y[i2]-Y[i1])/2;
scontro={time, i1, i2, diagAtt, p.first, i-1};
pq.push(scontro);
}
}
}
}
set<int> toKill;
int lastTime=1;
while(!pq.empty()){
array<int, 6> scontro=pq.top();
int currTime=scontro[0], nave1=scontro[1], nave2=scontro[2], diagType=scontro[3], diagInd=scontro[4], indDaRimuovere=scontro[5];
pq.pop();
if(currTime!=lastTime){
for(int shipToKill : toKill) isAlive[shipToKill]=false;
toKill.erase(toKill.begin(), toKill.end());
lastTime=currTime;
}
if(isAlive[nave1]!=isAlive[nave2]){
if(isAlive[nave1]) indDaRimuovere=diagonali[diagType][diagInd][indDaRimuovere].r; //se la prima nave è ancora in vita, allora devo rimuovere la seconda
pop(diagonali[diagType][diagInd], indDaRimuovere, diagType, diagInd);
}else{
if(isAlive[nave1]){
toKill.insert(nave1);
toKill.insert(nave2);
}
pop2(diagonali[diagType][diagInd], indDaRimuovere, indDaRimuovere+1, diagType, diagInd);
}
}
for(int shipToKill : toKill) isAlive[shipToKill]=false;
vector<int> ans;
for(int i=0; i<N; i++) if(isAlive[i]) ans.push_back(i+1);
return ans;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N;
cin >>N;
X.resize(N);
Y.resize(N);
vector<char> D(N);
for(int i=0; i<N; i++) cin >>X[i] >>Y[i] >>D[i];
vector<int> ans=affonda(N, D);
for(int i=0; i<ans.size(); i++) cout <<ans[i] <<'\n';
}
