#include<bits/stdc++.h>
#define int long long
#define f0r(i,n) for(int i = 0; i < n; i++)
#define FOR(i,k,n) for(int i = k; i < n; i++)
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define F first
#define S second
#define vi vector<int>
#define pii pair<int,int>
#define dout(x) cout<<x<<' '<<#x<<endl
#define dout2(x,y) cout<<x<<' '<<#x<<' '<<y<<' '<<#y<<endl
#define vout(v) cout<<#v<<": "; for(auto u : v)cout<<u<<' '; cout<<endl
using namespace std;
signed main(){
int n; cin>>n; map<int,set<pair<pii,int>>>m[6]; vector<pii>dir(n); map<pii,vi>has; vi X(n), Y(n);
has[mp(0,-1)]={1,3,4}; has[mp(0,1)]={0,2,4}; has[mp(1,0)]={0,3,5}; has[mp(-1,0)]={1,2,5};
f0r(i,n){
int x, y; cin>>x>>y; char c; cin>>c; X[i]=x,Y[i]=y;
if(c=='N')dir[i]=mp(0,-1); else if(c=='S')dir[i]=mp(0,1); else if(c=='E')dir[i]=mp(1,0); else dir[i]=mp(-1,0);
for(auto u : has[dir[i]]){
int d; if(u<2)d=x+y; else if(u<4)d=x-y; else if(u==4)d=x; else d=y; m[u][d].insert(mp(mp(x,y),i));
}
}
priority_queue<pair<int,pii>>q; f0r(i,6){
for(auto &[tt, s] : m[i]){
vector<pair<pii,int>>v; for(auto u : s)v.pb(u);
f0r(j,(int)v.size()-1){
pii d1 = dir[v[j].S], d2 = dir[v[j+1].S]; if(d1 != d2){
if(d1.F != d2.F){
if(d1.F > d2.F)q.push(mp(-abs(v[j].F.F - v[j+1].F.F)/(d1.F-d2.F), mp(v[j].S,v[j+1].S)));
}
else{
if(d1.S > d2.S)q.push(mp(-abs(v[j].F.S - v[j+1].F.S)/2, mp(v[j].S,v[j+1].S)));
}
}
}
}
}
int cur = -1; if(!q.empty())cur = q.top().F; set<int> tmp; vector<bool> vis(n);
while(1){
while(!q.empty() && q.top().F == cur){
int i1 = q.top().S.F, i2 = q.top().S.S; q.pop(); if(!vis[i1] && !vis[i2])tmp.insert(i1), tmp.insert(i2);
}
for(auto i : tmp){
vis[i] = 1; for(auto u : has[dir[i]]){
int d, x = X[i], y = Y[i];
if(u<2)d=x+y; else if(u<4)d=x-y; else if(u==4)d=x; else d=y;
auto it = m[u][d].find(mp(mp(x,y),i)); if(it != m[u][d].begin() && it != (--m[u][d].end())){
--it; int i1 = (*it).S; ++it; ++it; int i2 = (*it).S;
pii d1 = dir[i1], d2 = dir[i2]; if(d1 != d2){
if(d1.F != d2.F){
if(d1.F > d2.F)q.push(mp(-abs(X[i1] - X[i2])/(d1.F-d2.F), mp(i1,i2)));
}
else{
if(d1.S > d2.S)q.push(mp(-abs(Y[i1] - Y[i2])/2, mp(i1,i2)));
}
}
}
m[u][d].erase(mp(mp(x,y),i));
}
}
tmp.clear();
if(!q.empty())cur = q.top().F; else break;
}
f0r(i,n)if(!vis[i])cout<<i+1<<' ';
// vector<bool> vis(n); for(auto [a,b] : m){
// sort(b.begin(),b.end()); vi g; for(auto [A,d] : b){
// auto [x,y] = A;
// if(y==1)g.pb(d); else{
// if(!g.empty())vis[g.back()]=1,vis[d]=1,g.pop_back();
// }
// }
// } f0r(i,n)if(!vis[i])cout<<i+1<<' ';
}
