#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 1e6+1, inf = 2e18;
const int N = 2e5+1;
vector<char> c(N);
char curc1;
struct Rowmanager {
set<pii> best;
set<pii> ships;
void addship(int x,int id) {
ships.insert({x,id});
};
void remship(int x,int id) {
auto nxt = ships.upper_bound({x,id});
int nextv = -1,prevv = -1,previd=-1,nextid=-1;
if (nxt != ships.end()) {
if (c[id] != c[nxt->ss] && c[id] == curc1) best.erase({nxt->ff-x,id});
nextv = nxt->ff,nextid = nxt->ss;
}
--nxt;
if (nxt != ships.begin()) {
--nxt;
if (c[nxt->ss] != c[id] && c[nxt->ss] == curc1) best.erase({x-nxt->ff,nxt->ss});
prevv = nxt->ff;
previd = nxt->ss;
}
if (previd != -1 && nextid != -1) {
if (c[nextid] != c[previd] && c[previd]==curc1) best.insert({nextv-prevv,previd});
}
ships.erase({x,id});
}
void init() {
int prv = -1,prvv = -1;
for (auto it : ships) {
if (prv != -1) {
if (c[prv] != c[it.ss] && c[prv]==curc1) best.insert({it.ff-prvv,prv});
}
prvv = it.ff,prv = it.ss;
}
best.insert({inf,0});
}
};
struct Handler {
map<int,Rowmanager> rows;
set<pair<pii,int>> bests{{{inf,0},0}};
char c1,c2;
Handler(char C1,char C2) {
c1 = C1,c2 = C2;
};
void addship(int idx,int x,int id) {
curc1 = c1;
rows[idx].addship(x,id);
}
void remship(int idx,int x,int id) {
curc1 = c1;
bests.erase({*(rows[idx].best.begin()),idx});
rows[idx].remship(x,id);
bests.insert({*(rows[idx].best.begin()),idx});
}
void init() {
curc1 = c1;
for (auto& it : rows) {
it.ss.init();
bests.insert({*it.ss.best.begin(),it.ff});
}
}
pii getnext() {
return bests.begin()->ff;
}
};
void solve() {
int n;
cin >> n;
vi x(n+1),y(n+1);
Handler lr('E','W'),sn('S','N'),sw('S','W'),en('E','N'),es('E','S'),nw('N','W');
map<char,int> dirx,diry;
dirx['N'] = 0,diry['N'] = -1;
dirx['S'] = 0,diry['S'] = 1;
dirx['E'] = 1,diry['E'] = 0;
dirx['W'] = -1,diry['W'] = 0;
for (int i=1;i<=n;i++){
cin >> x[i] >> y[i];
cin >> c[i];
if (c[i] == 'E' || c[i] == 'W') lr.addship(y[i],x[i]/2,i);
if (c[i] == 'S' || c[i] == 'N') sn.addship(x[i],y[i]/2,i);
if (c[i] == 'E' || c[i] == 'N') en.addship(x[i]-y[i],x[i],i);
if (c[i] == 'S' || c[i] == 'W') sw.addship(x[i]-y[i],x[i],i);
if (c[i] == 'E' || c[i] == 'S') es.addship(y[i]+x[i],x[i],i);
if (c[i] == 'N' || c[i] == 'W') nw.addship(y[i]+x[i],x[i],i);
}
lr.init();
sn.init();
en.init();
sw.init();
es.init();
nw.init();
vi dead(n+1,0);
vector<char> dirs{'N','S','E','W'};
map<pii,int> ids;
for (int i=1;i<=n;i++) ids[{x[i],y[i]}] = i;
auto kill = [&](int ship) -> void {
if (dead[ship]) return;
dead[ship] = 1;
if (c[ship] == 'E' || c[ship] == 'W') lr.remship(y[ship],x[ship]/2,ship);
if (c[ship] == 'S' || c[ship] == 'N') sn.remship(x[ship],y[ship]/2,ship);
if (c[ship] == 'E' || c[ship] == 'N') en.remship(x[ship]-y[ship],x[ship],ship);
if (c[ship] == 'S' || c[ship] == 'W') sw.remship(x[ship]-y[ship],x[ship],ship);
if (c[ship] == 'E' || c[ship] == 'S') es.remship(x[ship]+y[ship],x[ship],ship);
if (c[ship] == 'N' || c[ship] == 'W') nw.remship(x[ship]+y[ship],x[ship],ship);
};
int nn = n;
while(nn--) {
pii nextcollision = min({lr.getnext(),sn.getnext(),en.getnext(),sw.getnext(),es.getnext(),nw.getnext()});
int t = nextcollision.ff,id = nextcollision.ss;
if (t >= inf) break;
pii where = {x[id]+dirx[c[id]]*t,y[id]+diry[c[id]]*t};
for (auto it : dirs) {
pii togo = {where.ff+t*dirx[it],where.ss+t*diry[it]};
if (ids.count(togo)){
int vv = ids[togo];
if (where == pii{x[vv]+dirx[c[vv]]*t,y[vv]+diry[c[vv]]*t}) {
kill(vv);
}
}
}
}
for (int i=1;i<=n;i++) {
if (!dead[i]) cout << i << '\n';
}
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int t = 1;
//cin >> t;
while (t --> 0) solve();
}
