#include<bits/stdc++.h>
using namespace std;
#define int long long
struct intersect {
int distParc,premBat,deuzBat;
bool operator < (const intersect& autre) const {
return distParc>autre.distParc;
}
};
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];
set<int> listeVal[4];
unordered_map<int,int> reNum[4];
vector<pair<int,int>> corres;
set<pair<int,int>> posBat[MAX_BAT][6];
priority_queue<intersect> possi;
vector<vector<bool>> pris={{false,true,true,false},
{true,false,false,true},
{false,true,false,true},
{false,false,true,true},
{true,true,false,false},
{true,false,true,false}};
vector<int> numHache={0,0,1,2,2,3};
vector<pair<int,int>> pente={{1,1},
{1,1},
{0,1},
{1,-1},
{1,-1},
{1,0}};
vector<pair<int,int>> combin={{1,0},
{1,0},
{1,0},
{1,0},
{1,0},
{0,1}};
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 init(int idSom,int idSens) {
int taille=posBat[idSom][idSens].size();
if (taille==0) {
return;
}
auto it=posBat[idSom][idSens].begin();
int bat1,bat2,dist;
for (int i=0;i<taille-1;i++) {
bat1=(*it).second;
it++;
bat2=(*it).second;
dist=calcInter(bat1,bat2);
if (dist!=INFINI) {
possi.push({dist,bat1,bat2});
}
}
}
void suppr(int idSom,int idSens,int batSup,int som) {
//cout<<"?"<<idSom<<" "<<idSens<<" "<<batSup<<" "<<som<<endl;
auto it=posBat[idSom][idSens].lower_bound({som,batSup});
if (it==posBat[idSom][idSens].end() or (*it)!=make_pair(som,batSup)) {
return;
}
//cout<<"?"<<idSom<<" "<<idSens<<" "<<batSup<<" "<<som<<endl;
posBat[idSom][idSens].erase(it);
it=posBat[idSom][idSens].lower_bound({som,batSup});
if (it==posBat[idSom][idSens].end() or it==posBat[idSom][idSens].begin()) {
return;
}
int bat1,bat2=(*it).second,dist;
it--;
bat1=(*it).second;
dist=calcInter(bat1,bat2);
//cout<<idSens<<" : "<<bat1<<" "<<bat2<<" "<<dist<<endl;
if (dist!=INFINI) {
possi.push({dist,bat1,bat2});
}
}
void maj(int batSup,int dist) {
//cout<<"!"<<batSup<<" "<<dist<<endl;
dateInter[batSup]=dist;
for (int j=0;j<6;j++) {
if (pris[j][direc[batSup]]) {
suppr(reNum[numHache[j]][coord[batSup].first*pente[j].first+coord[batSup].second*pente[j].second],j,batSup,coord[batSup].first*combin[j].first+coord[batSup].second*combin[j].second);
}
}
}
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;
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;
}
listeVal[0].insert(coord[i].first+coord[i].second);
listeVal[1].insert(coord[i].second);
listeVal[2].insert(coord[i].first-coord[i].second);
listeVal[3].insert(coord[i].first);
dateInter[i]=INFINI;
}
int numDeCeType;
for (int i=0;i<4;i++) {
numDeCeType=0;
for (int j:listeVal[i]) {
reNum[i][j]=numDeCeType;
numDeCeType++;
}
}
for (int i=1;i<=nbBat;i++) {
for (int j=0;j<6;j++) {
if (pris[j][direc[i]]) {
posBat[reNum[numHache[j]][coord[i].first*pente[j].first+coord[i].second*pente[j].second]][j].insert({coord[i].first*combin[j].first+coord[i].second*combin[j].second,i});
}
}
}
for (int i=0;i<nbBat;i++) {
for (int j=0;j<6;j++) {
init(i,j);
}
}
int bat1,bat2,dist;
while (!possi.empty()) {
dist=possi.top().distParc;
bat1=possi.top().premBat;
bat2=possi.top().deuzBat;
//cout<<bat1<<" "<<bat2<<" "<<dist<<endl;
possi.pop();
if (dateInter[bat1]>=dist and dateInter[bat2]>=dist) {
maj(bat1,dist);
maj(bat2,dist);
}
}
for (int i=1;i<=nbBat;i++) {
if (dateInter[i]==INFINI) {
cout<<i<<"\n";
}
}
return 0;
}
