#include <bits/stdc++.h>
#define int long long
using namespace std;
struct Point {
int x, y; char dir;
};
struct Collision {
int id1, id2, temps;
};
bool operator < (const Collision& a, const Collision& b) {
return a.temps > b.temps;
}
int nbPoints;
vector<Point> points;
vector<bool> estEnVie;
priority_queue<Collision> collisions;
struct Point1D {
int id, pos, sens;
};
bool operator < (const Point1D& a, const Point1D& b) {
return a.pos < b.pos;
}
struct Diagonale {
list<Point1D> elems;
map<int, list<Point1D>::iterator> its;
void etudie(const Point1D& a, const Point1D& b) {
if(a.sens > b.sens) {
collisions.push({a.id, b.id, b.pos - a.pos});
}
}
void init() {
vector<Point1D> elemsVec(elems.begin(), elems.end());
sort(elemsVec.begin(), elemsVec.end());
elems = list<Point1D>(elemsVec.begin(), elemsVec.end());
for(auto it = elems.begin();it != elems.end();it++) {
its[it->id] = it;
if(next(it) != elems.end()) {
etudie(*it, *next(it));
}
}
}
void supprimer(int id) {
auto it = its[id];
auto itSuiv = elems.erase(it);
if(itSuiv != elems.begin() && itSuiv != elems.end()) {
auto itPrec = prev(itSuiv);
etudie(*itPrec, *itSuiv);
}
}
};
vector<vector<Diagonale*>> diagonales;
vector<map<int, Diagonale*>> directions(6);
void ajoute(int dir, int coord1, int coord2, int id, int sens) {
if(!directions[dir].count(coord1)) directions[dir][coord1] = new Diagonale{};
directions[dir][coord1]->elems.push_back({id, coord2, sens});
diagonales[id].push_back(directions[dir][coord1]);
}
signed main() {
ios_base::sync_with_stdio(false);
cin >> nbPoints;
estEnVie = vector<bool>(nbPoints, true);
diagonales = vector<vector<Diagonale*>>(nbPoints);
points = vector<Point>(nbPoints);
for(int iPoint = 0;iPoint < nbPoints;iPoint++) {
Point& p = points[iPoint];
cin >> p.x >> p.y >> p.dir;
if(p.dir == 'W' || p.dir == 'E') ajoute(4, p.y, p.x, iPoint, (p.dir == 'W')?-1:1);
if(p.dir == 'N' || p.dir == 'S') ajoute(5, p.x, p.y, iPoint, (p.dir == 'N')?-1:1);
if(p.dir == 'N' || p.dir == 'W') ajoute(0, p.x + p.y, p.y - p.x, iPoint, (p.dir == 'N')?-1:1);
if(p.dir == 'S' || p.dir == 'E') ajoute(2, p.x + p.y, p.y - p.x, iPoint, (p.dir == 'S')?1:-1);
if(p.dir == 'E' || p.dir == 'N') ajoute(1, p.y - p.x, p.x + p.y, iPoint, (p.dir == 'N')?-1:1);
if(p.dir == 'W' || p.dir == 'S') ajoute(3, p.y - p.x, p.x + p.y, iPoint, (p.dir == 'S')?1:-1);
}
for(int dir = 0;dir < 6;dir++) {
for(auto diag : directions[dir]) {
diag.second->init();
}
}
while(!collisions.empty()) {
vector<int> aSupprimer;
int temps = collisions.top().temps;
while(!collisions.empty() && collisions.top().temps == temps) {
Collision col = collisions.top();
collisions.pop();
if(estEnVie[col.id1] && estEnVie[col.id2]) {
aSupprimer.push_back(col.id1);
aSupprimer.push_back(col.id2);
}
}
sort(aSupprimer.begin(), aSupprimer.end());
aSupprimer.erase(unique(aSupprimer.begin(), aSupprimer.end()), aSupprimer.end());
for(int id : aSupprimer) {
estEnVie[id] = false;
for(Diagonale* diag : diagonales[id]) {
diag->supprimer(id);
}
}
while(!collisions.empty()) {
Collision col = collisions.top();
if(estEnVie[col.id1] && estEnVie[col.id2]) break;
else collisions.pop();
}
}
for(int iPoint = 0;iPoint < nbPoints;iPoint++) {
if(estEnVie[iPoint]) {
cout << iPoint + 1 << " ";
}
}
cout << endl;
return 0;
}
