#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(); }