#include <bits/stdc++.h>
#define int long long
using namespace std;
struct Point {
int x, y; char dir;
};
struct Diagonale;
struct Collision {
int id1, id2, temps;
Diagonale* diag;
};
bool operator < (const Collision& a, const Collision& b) {
return a.temps > b.temps;
}
int nbPoints;
vector<Point> points;
vector<bool> estEnVie;
struct Point1D {
int id, pos, sens;
};
bool operator < (const Point1D& a, const Point1D& b) {
return a.pos < b.pos;
}
struct Diagonale {
Collision suiv_collision;
priority_queue<Collision> collisions;
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, this});
}
}
void update() {
while(!collisions.empty()) {
Collision col = collisions.top();
if(estEnVie[col.id1] && estEnVie[col.id2]) break;
else collisions.pop();
}
if(collisions.empty()) suiv_collision = {-1, -1, -1, nullptr};
else suiv_collision = collisions.top();
}
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));
}
}
update();
}
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);
}
update();
}
};
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]);
}
priority_queue<Collision> collisions;
void ajoute(Collision col) {
if(col.temps != -1) {
collisions.push(col);
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin >> nbPoints;
estEnVie = vector<bool>(nbPoints, true);
diagonales = vector<vector<Diagonale*>>(nbPoints);
for(int iPoint = 0;iPoint < nbPoints;iPoint++) {
int x, y; char dir;
cin >> x >> y >> dir;
points.push_back({x, y, dir});
}
for(int iPoint = 0;iPoint < nbPoints;iPoint++) {
Point& p = points[iPoint];
if(p.dir == 'N' || p.dir == 'S') ajoute(0, p.y, p.x, iPoint, (p.dir == 'N')?-1:1);
if(p.dir == 'W' || p.dir == 'E') ajoute(1, p.x, p.y, iPoint, (p.dir == 'W')?-1:1);
if(p.dir == 'N' || p.dir == 'W') ajoute(2, p.x + p.y, p.y - p.x, iPoint, (p.dir == 'N')?-1:1);
if(p.dir == 'S' || p.dir == 'E') ajoute(3, p.x + p.y, p.y - p.x, iPoint, (p.dir == 'S')?1:-1);
if(p.dir == 'E' || p.dir == 'N') ajoute(4, p.y - p.x, p.x + p.y, iPoint, (p.dir == 'N')?-1:1);
if(p.dir == 'W' || p.dir == 'S') ajoute(5, p.y - p.x, p.x + p.y, iPoint, (p.dir == 'S')?1:-1);
}
for(int dir = 0;dir < 6;dir++) {
for(auto it = directions[dir].begin();it != directions[dir].end();it++) {
it->second->init();
ajoute(it->second->suiv_collision);
}
}
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);
if(!col.diag->collisions.empty()) {
col.diag->collisions.pop();
col.diag->update();
ajoute(col.diag->suiv_collision);
}
}
}
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);
ajoute(diag->suiv_collision);
}
}
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;
}
