#include <bits/stdc++.h>
#define int long long
using namespace std;
struct Point {
int x, y, dir;
};
int NORD = 0, OUEST = 1, SUD = 2, EST = 3;
map<char, int> to_dir = {{'N', NORD}, {'W', OUEST}, {'S', SUD}, {'E', EST}};
vector<Point> dirs = {{0, -1, NORD}, {-1, 0, OUEST}, {0, 1, SUD}, {1, 0, EST}};
pair<int, int> rotate(pair<int, int> pt) {
return {pt.first + pt.second, pt.second - pt.first};
}
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;
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});
}
}
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};
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]);
}
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 type;
cin >> x >> y >> type;
points.push_back({x, y, to_dir[type]});
}
for(int iPoint = 0;iPoint < nbPoints;iPoint++) {
Point& p = points[iPoint];
pair<int, int> coords = {p.x, p.y};
pair<int, int> dir = {dirs[p.dir].x, dirs[p.dir].y};
if(dir.first != 0) ajoute(4, coords.second, coords.first, iPoint, dir.first);
if(dir.second != 0) ajoute(5, coords.first, coords.second, iPoint, dir.second);
if(p.dir == NORD || p.dir == OUEST) {
ajoute(0, coords.first + coords.second, coords.second - coords.first, iPoint, (p.dir == NORD)?-1:1);
}
if(p.dir == EST || p.dir == NORD) {
ajoute(1, coords.second - coords.first, coords.first + coords.second, iPoint, (p.dir == NORD)?-1:1);
}
if(p.dir == SUD || p.dir == OUEST) {
ajoute(2, coords.first + coords.second, coords.second - coords.first, iPoint, (p.dir == SUD)?1:-1);
}
if(p.dir == EST || p.dir == SUD) {
ajoute(3, coords.second - coords.first, coords.first + coords.second, iPoint, (p.dir == SUD)?1:-1);
}
}
priority_queue<Collision> collisions;
for(int dir = 0;dir < 6;dir++) {
for(auto it = directions[dir].begin();it != directions[dir].end();it++) {
it->second->init();
if(it->second->suiv_collision.temps != -1) {
collisions.push(it->second->suiv_collision);
}
}
}
while(!collisions.empty()) {
vector<int> aSupprimer;
int temps = collisions.top().temps;
//cerr << "time: " << temps << endl;
while(!collisions.empty() && collisions.top().temps == temps) {
Collision col = collisions.top();
collisions.pop();
if(estEnVie[col.id1] && estEnVie[col.id2]) {
//cerr << col.id1 + 1 << " " << col.id2 + 1 << endl;
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) {
//cerr << 1 + id << " ";
estEnVie[id] = false;
for(Diagonale* diag : diagonales[id]) {
diag->supprimer(id);
}
}
//cerr << endl;
for(int id : aSupprimer) {
for(Diagonale* diag : diagonales[id]) {
if(diag->suiv_collision.temps != -1) {
collisions.push(diag->suiv_collision);
}
}
}
while(!collisions.empty()) {
Collision col = collisions.top();
if(estEnVie[col.id1] && estEnVie[col.id2]) break;
else collisions.pop();
}
}
for(int dir = 0;dir < 6;dir++) {
for(auto it = directions[dir].begin();it != directions[dir].end();it++) {
delete it->second;
}
}
for(int iPoint = 0;iPoint < nbPoints;iPoint++) {
if(estEnVie[iPoint]) {
cout << iPoint + 1 << " ";
}
}
cout << endl;
return 0;
}
