#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
#define ll long long int
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define en cout << '\n'
const int N = 2e5+1;
int n, tp[N], arr[N][2];
vector<array<int, 3>> a[4]; // 'E', 'W', 'N', 'S'
int to[4][3]={
{0, 2, 5},
{1, 3, 5},
{1, 2, 4},
{0, 3, 4}
};
int f(int x, int y, int p){
if(p < 2) return x + y;
if(p < 4) return x - y;
if(p == 4) return y;
return x;
}
bool good(array<int, 3> x, array<int, 3> y){
if(tp[x[2]] == tp[y[2]]) return false;
if(x[0] > y[0]) swap(x, y);
else if(x[0] == y[0]){
if(x[1] > y[1]) swap(x, y);
}
// cout << x[0] << ' ' << x[1] << ' ' << x[2] << '\n';
// cout << y[0] << ' ' << y[1] << ' ' << y[2] << '\n';
if(x[1] == y[1]){
return tp[x[2]] == 3;
}
if(x[0] == y[0]){
return tp[x[2]] == 0;
}
if(x[0] + x[1] == y[0] + y[1]){
return (tp[x[2]] == 3 && tp[y[2]] == 0) || (tp[x[2]] == 1 && tp[y[2]] == 2);
}
return (tp[x[2]] == 0 && tp[y[2]] == 2) || (tp[x[2]] == 3 && tp[y[2]] == 1);
}
int calc(array<int, 3> x, array<int, 3> y){
if(x[0] > y[0]) swap(x, y);
else if(x[0] == y[0]){
if(x[1] > y[1]) swap(x, y);
}
if(x[1] == y[1]){
return abs(x[0]-y[0])/2;
}
if(x[0] == y[0]){
return abs(x[1]-y[1])/2;
}
return abs(x[0]-y[0]);
}
map<int, set<array<int, 3>>> M[6];
void ext(int i, int j, int idx, priority_queue<array<int, 3>> &Q){
auto it = M[i][j].lower_bound(array<int,3>{arr[idx][0], arr[idx][1], idx});
if(next(it) != M[i][j].end() && it != M[i][j].begin()){
auto it2 = prev(it);
auto it3 = next(it);
if(good((*it2), (*it3))){
Q.push({-calc((*it2), (*it3)), (*it2)[2], (*it3)[2]});
}
}
M[i][j].erase(it);
}
void solve(){
cin >> n;
for(int i = 1; i <= n; ++i){
int x, y; char c; cin >> x >> y >> c;
swap(x, y);
arr[i][0] = x;
arr[i][1] = y;
if(c == 'E') a[0].pb({x, y, i}), tp[i] = 0;
if(c == 'W') a[1].pb({x, y, i}), tp[i] = 1;
if(c == 'N') a[2].pb({x, y, i}), tp[i] = 2;
if(c == 'S') a[3].pb({x, y, i}), tp[i] = 3;
}
// 'E', 'S' / 'N', 'W' / 'E', 'N' / 'W', 'S' / 'N', 'S' / 'E', 'W'
for(auto p: a[0]){
for(int i = 0; i < 3; ++i){
M[to[0][i]][f(p[0], p[1], to[0][i])].insert(p);
}
}
for(auto p: a[1]){
for(int i = 0; i < 3; ++i){
M[to[1][i]][f(p[0], p[1], to[1][i])].insert(p);
}
}
for(auto p: a[2]){
for(int i = 0; i < 3; ++i){
// cout << to[2][i] << ' ' << f(p[0], p[1], to[2][i]) << '\n';
M[to[2][i]][f(p[0], p[1], to[2][i])].insert(p);
}
}
for(auto p: a[3]){
for(int i = 0; i < 3; ++i){
// cout << p[0] << ' ' << p[1] << ' ' << p[2] << '\n';
// cout << to[3][i] << ' ' << f(p[0], p[1], to[3][i]) << '\n';
M[to[3][i]][f(p[0], p[1], to[3][i])].insert(p);
}
}
vector<bool> ded(n + 1);
priority_queue<array<int, 3>> Q;
for(int i = 0; i < 6; ++i){
for(auto &S: M[i]){
auto it = S.ss.begin();
while(next(it) != S.ss.end()){
auto v = *it;
auto u = *next(it);
if(good(u, v)){
// cout << v[0] << ' ' << v[1] << ' ' << v[2] << '\n';
// cout << u[0] << ' ' << u[1] << ' ' << u[2] << '\n';
// cout << endl;
Q.push({-calc(u, v), v[2], u[2]});
}
it = next(it);
}
}
}
// cout << "f" << endl;
int last = -1;
vector<int> rem;
while(!Q.empty() || !rem.empty()){
if(Q.empty()){
sort(all(rem));
rem.erase(unique(all(rem)), rem.end());
for(int idx: rem){
// cout << idx << endl;
int t = tp[idx];
for(int j = 0; j < 3; ++j){
ext(to[t][j], f(arr[idx][0], arr[idx][1], to[t][j]), idx, Q);
}
ded[idx] = 1;
}
rem.clear();
continue;
}
auto P = Q.top();
Q.pop();
if(-P[0] != last && !rem.empty()){
sort(all(rem));
rem.erase(unique(all(rem)), rem.end());
for(int idx: rem){
int t = tp[idx];
for(int j = 0; j < 3; ++j){
ext(to[t][j], f(arr[idx][0], arr[idx][1], to[t][j]), idx, Q);
}
ded[idx] = 1;
}
rem.clear();
Q.push(P);
continue;
}
if(ded[P[1]] || ded[P[2]]) continue;
// cout << P[1] << ' ' << P[2] << '\n';
rem.pb(P[1]);
rem.pb(P[2]);
last = -P[0];
}
for(int i = 1; i <= n; ++i) if(ded[i] == 0) cout << i << '\n';
}
int main() {
cin.tie(0); ios::sync_with_stdio(0);
solve();
return 0;
}
