#include<bits/stdc++.h>
using namespace std;
// #define int long long
#define pb push_back
#define fr first
#define sc second
const int maxn = 1e5+10;
const int inf = 1e9;
int H, L, n, x[maxn], y[maxn], block[maxn];
int xc[maxn], yc[maxn], tc[maxn];
char d[maxn];
priority_queue<array<int,4>,vector<array<int,4>>,greater<array<int,4>>> pq;
map<int,set<pair<int,int>>> pos[10];
char di[10], dj[10];
int dist2(int tp, int i, int j) {
if(tp <= 3) {
return 2*abs(x[i]-x[j]);
}
else if(tp == 4) {
return abs(x[i]-x[j]);
}
else if (tp == 5){
return abs(y[i]-y[j]);
}
else if(tp <= 7) {
return 2*abs(x[i]-xc[j]);
}
else {
return 2*abs(y[i]-yc[j]);
}
}
int cntcol;
void addcol(int X, int Y, int T) {
xc[cntcol] = X;
yc[cntcol] = Y;
tc[cntcol] = T;
for(int tp = 6; tp <= 9; tp++) {
if(tp == 6 or tp == 8) {
auto it = pos[tp][(tp == 6 ? Y : X)].upper_bound({(tp == 6 ? X : Y)-T,inf});
if(it != pos[tp][(tp == 6 ? Y : X)].begin()) {
int i = prev(it)->sc;
pq.push({dist2(tp,i,cntcol),i,cntcol,tp});
}
}
else {
auto it = pos[tp][(tp == 7 ? Y : X)].upper_bound({(tp == 7 ? X : Y)+T,-inf});
if(it != pos[tp][(tp == 7 ? Y : X)].end()) {
int i = it->sc;
pq.push({dist2(tp,i,cntcol),i,cntcol,tp});
}
}
}
cntcol++;
}
signed main(){
cin.tie(0)->sync_with_stdio(0);
di[0] = 'N';
dj[0] = 'W';
di[1] = 'E';
dj[1] = 'S';
di[2] = 'E';
dj[2] = 'N';
di[3] = 'S';
dj[3] = 'W';
di[4] = 'E';
dj[4] = 'W';
di[5] = 'S';
dj[5] = 'N';
di[6] = 'E';
dj[6] = 'X';
di[7] = 'W';
dj[7] = 'X';
di[8] = 'S';
dj[8] = 'X';
di[9] = 'N';
dj[9] = 'X';
cin >> n;
for(int i = 0; i < n; i++) {
cin >> x[i] >> y[i] >> d[i];
if(d[i] == 'N') {
pos[0][x[i]+y[i]].insert({x[i],i});
pos[2][x[i]-y[i]].insert({x[i],i});
pos[5][x[i]].insert({y[i],i});
pos[9][x[i]].insert({y[i],i});
}
if(d[i] == 'W') {
pos[0][x[i]+y[i]].insert({x[i],i});
pos[3][x[i]-y[i]].insert({x[i],i});
pos[4][y[i]].insert({x[i],i});
pos[7][y[i]].insert({x[i],i});
}
if(d[i] == 'E') {
pos[1][x[i]+y[i]].insert({x[i],i});
pos[2][x[i]-y[i]].insert({x[i],i});
pos[4][y[i]].insert({x[i],i});
pos[6][y[i]].insert({x[i],i});
}
if(d[i] == 'S') {
pos[1][x[i]+y[i]].insert({x[i],i});
pos[3][x[i]-y[i]].insert({x[i],i});
pos[5][x[i]].insert({y[i],i});
pos[8][x[i]].insert({y[i],i});
}
}
for(int tp = 0; tp <= 5; tp++) {
int LL,R;
for(auto X : pos[tp]) {
int v = X.fr;
if(pos[tp][v].size() == 0) continue;
auto it = pos[tp][v].begin();
while(next(it) != pos[tp][v].end()) {
int i = it->sc;
it++;
int j = it->sc;
if(d[i] == di[tp] and d[j] == dj[tp]) {
pq.push({dist2(tp,i,j),i,j,tp});
}
}
}
}
while(pq.size()) {
int i = pq.top()[1];
int j = pq.top()[2];
int tp = pq.top()[3];
pq.pop();
int qual;
if(tp == 0) {
qual = x[i]+y[i];
}
else if(tp == 1) {
qual = x[i]+y[i];
}
else if(tp == 2) {
qual = x[i]-y[i];
}
else if(tp == 3) {
qual = x[i]-y[i];
}
else if(tp == 4) {
qual = y[i];
}
else if(tp == 5) {
qual = x[i];
}
else if(tp == 6) {
qual = y[i];
}
else if(tp == 7) {
qual = y[i];
}
else if(tp == 8) {
qual = x[i];
}
else if(tp == 9) {
qual = x[i];
}
if(block[i]) {
auto it = pos[tp][qual].find({(tp == 5 or tp >= 8 ? y[i] : x[i]),i});
if(it == pos[tp][qual].end()) {continue;}
if(tp == 7 or tp == 9) {
if(next(it) != pos[tp][qual].end()) {
int i1 = next(it)->sc;
if(d[i1] == di[tp]) {
pq.push({dist2(tp,i1,j),i1,j,tp});
}
}
}
else {
if(it != pos[tp][qual].begin()) {
int i1 = prev(it)->sc;
if(d[i1] == di[tp]) {
pq.push({dist2(tp,i1,j),i1,j,tp});
}
}
}
pos[tp][qual].erase(it);
}
else if(tp <= 5 and block[j]) {
auto it = pos[tp][qual].find({(tp == 5 or tp >= 8 ? y[j] : x[j]),j});
if(it == pos[tp][qual].end()) {continue;}
if(next(it) != pos[tp][qual].end()) {
int j1 = next(it)->sc;
if(d[j1] == dj[tp]) {
pq.push({dist2(tp,i,j1),i,j1,tp});
}
}
pos[tp][qual].erase(it);
}
else if(tp <= 5) {
block[i] = 1;
block[j] = 1;
auto it = pos[tp][qual].find({(tp == 5 or tp >= 8 ? y[i] : x[i]),i});
int i1 = -1;
if(it != pos[tp][qual].begin()) {
i1 = prev(it)->sc;
}
it++;
int j1 = -1;
if(next(it) != pos[tp][qual].end()) {
j1 = next(it)->sc;
}
pos[tp][qual].erase({(tp == 5 or tp >= 8 ? y[i] : x[i]),i});
pos[tp][qual].erase({(tp == 5 or tp >= 8 ? y[j] : x[j]),j});
if(i1 != -1 and j1 != -1 and d[i1] == di[tp] and d[j1] == dj[tp]) {
pq.push({dist2(tp,i1,j1),i1,j1,tp});
}
// colocar essa colisao em 6 7 8 9
// if(tp == 0 or tp == 3) {
// addcol(x[i],y[j],abs(x[i]-x[j]));
// }
// else if(tp == 1 or tp == 2) {
// addcol(x[j],y[i],abs(x[i]-x[j]));
// }
// else if(tp == 4) {
// addcol((x[i]+x[j]+1)/2,y[i],(abs(x[i]-x[j])+1)/2);
// }
// else {
// addcol(x[i],(y[i]+y[j])/2,(abs(y[i]-y[j])+1)/2);
// }
}
else {
block[i] = 1;
auto it = pos[tp][qual].find({(tp == 5 or tp >= 8 ? y[i] : x[i]),i});
int i1 = -1;
if(tp == 6 or tp == 8) {
if(it != pos[tp][qual].begin()) {
i1 = prev(it)->sc;
}
}
else {
if(next(it) != pos[tp][qual].end()) {
i1 = next(it)->sc;
}
}
pos[tp][qual].erase({(tp == 5 or tp >= 8 ? y[i] : x[i]),i});
if(i1 != -1) {
pq.push({dist2(tp,i1,j),i1,j,tp});
}
}
}
for(int i = 0; i < n; i++) {
if(!block[i]) {
cout << i+1 << " ";
}
}
}
