#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define pb push_back #define eb emplace_back using namespace std; typedef long long ll; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } const int maxn=2e5+10; int n,x[maxn],y[maxn],vis[maxn];char op[maxn]; int dist(int u,int v){return abs(x[u]-x[v])+abs(y[u]-y[v]);} void slv(){ n=read(); up(i,1,n)x[i]=read(),y[i]=read(),op[i]=getchar(); map<int,set<pi> >M1,M2,M3,M4,M5,M6; up(i,1,n)if(op[i]=='E'||op[i]=='W')M1[y[i]].insert({x[i],i}); up(i,1,n)if(op[i]=='N'||op[i]=='S')M2[x[i]].insert({y[i],i}); up(i,1,n)if(op[i]=='S'||op[i]=='W')M3[x[i]-y[i]].insert({x[i],i}); up(i,1,n)if(op[i]=='S'||op[i]=='E')M4[x[i]+y[i]].insert({x[i],i}); up(i,1,n)if(op[i]=='N'||op[i]=='W')M5[x[i]+y[i]].insert({x[i],i}); up(i,1,n)if(op[i]=='N'||op[i]=='E')M6[x[i]-y[i]].insert({x[i],i}); set<tuple<int,int,int> >q; auto work=[&](map<int,set<pi> >&M,char op1,char op2){ for(auto [a,b]:M){ int la=0; for(auto [x,id]:b){ if(op[id]==op2&&op[la]==op1)q.insert(make_tuple(dist(la,id),la,id)); la=id; } } }; work(M1,'E','W'),work(M2,'S','N'),work(M3,'S','W'),work(M4,'E','S'),work(M5,'N','W'),work(M6,'E','N'); auto del=[&](map<int,set<pi> >&M,char op1,char op2,int p,int va,int va2){ if(op[p]!=op1&&op[p]!=op2)return; M[va].erase(m_p(va2,p)); if(op[p]==op1){ auto it=M[va].lower_bound(m_p(va2,p)); auto it2=it; if(it2==M[va].end()||op[(*it2).p2]==op1)return; int to=(*it2).p2; q.erase(make_tuple(dist(p,to),p,to)); if(it!=M[va].begin()&&op[(*(--it)).p2]==op1){ int id=(*it).p2; q.insert(make_tuple(dist(id,to),id,to)); } }else{ auto it=M[va].lower_bound(m_p(va2,p)); auto it2=it; if(it2==M[va].begin()||op[(*(--it2)).p2]==op2)return; int to=(*it2).p2; q.erase(make_tuple(dist(to,p),to,p)); if(it!=M[va].end()&&op[(*it).p2]==op2){ int id=(*it).p2; q.insert(make_tuple(dist(to,id),to,id)); } } }; auto delnd=[&](int u){ if(vis[u])return;vis[u]=1; del(M1,'E','W',u,y[u],x[u]); del(M2,'S','N',u,x[u],y[u]); del(M3,'S','W',u,x[u]-y[u],x[u]); del(M4,'E','S',u,x[u]+y[u],x[u]); del(M5,'N','W',u,x[u]+y[u],x[u]); del(M6,'E','N',u,x[u]-y[u],x[u]); }; while(!q.empty()){ int tim=get<0>(*q.begin()); vector<int>id; while(q.size()&&get<0>(*q.begin())==tim) id.eb(get<1>(*q.begin())),id.eb(get<2>(*q.begin())),q.erase(q.begin()); for(int i:id)delnd(i); } up(i,1,n)if(!vis[i])printf("%d\n",i); } int main(){ // freopen("a.in","r",stdin),freopen("a.out","w",stdout); slv(); return 0; }