// 01001100 01001111 01010100 01000001 \\
// \\
// ╦ ╔═╗╔╦╗╔═╗ \\
// ║ ║ ║ ║ ╠═╣ \\
// ╩═╝╚═╝ ╩ ╩ ╩ \\
// \\
// 01001100 01001111 01010100 01000001 \\
#include <bits/stdc++.h>
using namespace std;
#define N 1000001
#define nl '\n'
#define ff first
#define ss second
#define add insert
#define ll long long
#define ld long double
#define terminator main
#define pll pair<ll,ll>
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define L0TA ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
// N E S W
int a[N];
int b[N];
int c[N];
map<int, vector<int>> t;
map<int, set<int>> xy[4];
map<int, set<int>> yx[4];
map<int, set<int>> x[4][2];
map<int, set<int>> y[4][2];
int lst(set<int> & s, int v){
auto it = s.upper_bound(v);
if(it == s.begin()) return -1;
return *(--it);
}
int nxt(set<int> & s, int v){
auto it = s.upper_bound(v);
if(it == s.end()) return -1;
return *it;
}
int crash(int p, int q, int r){
int m, ans;
ans = 1e9 + 1;
if(r == 0){
m = lst(x[2][q & 1][p], q);
if(m >= 0) ans = min(ans, (q - m) / 2);
m = lst(xy[3][p + q], q);
if(m >= 0) ans = min(ans, (q - m));
m = lst(yx[1][p - q], p);
if(m >= 0) ans = min(ans, (p - m));
}
if(r == 1){
m = nxt(y[3][p & 1][q], p);
if(m >= 0) ans = min(ans, (m - p) / 2);
m = lst(xy[2][p + q], q);
if(m >= 0) ans = min(ans, (q - m));
m = nxt(yx[0][p - q], p);
if(m >= 0) ans = min(ans, (m - p));
}
if(r == 2){
m = nxt(x[0][q & 1][p], q);
if(m >= 0) ans = min(ans, (m - q) / 2);
m = nxt(xy[1][p + q], q);
if(m >= 0) ans = min(ans, (m - q));
m = nxt(yx[3][p - q], p);
if(m >= 0) ans = min(ans, (m - p));
}
if(r == 3){
m = lst(x[1][p & 1][q], p);
if(m >= 0) ans = min(ans, (p - m) / 2);
m = nxt(xy[0][p + q], q);
if(m >= 0) ans = min(ans, (m - q));
m = lst(yx[2][p - q], p);
if(m >= 0) ans = min(ans, (p - m));
}
return ans;
}
void solve(){
char d;
int n, m, p, q, r;
cin >> n;
for (int i = 1; i <= n; i++){
cin >> p >> q >> d;
a[i] = p, b[i] = q;
if(d == 'N') c[i] = 0;
if(d == 'E') c[i] = 1;
if(d == 'S') c[i] = 2;
if(d == 'W') c[i] = 3;
xy[c[i]][p + q].add(q);
yx[c[i]][p - q].add(p);
x[c[i]][q & 1][p].add(q);
y[c[i]][p & 1][q].add(p);
}
for(int i = 1; i <= n; i++)
t[crash(a[i], b[i], c[i])].append(i);
vector<int> v;
while(!t.empty()){
m = (*t.begin()).ff;
if(m > 1e9) break;
for(auto & i : t[m]){
r = crash(a[i], b[i], c[i]);
if(r == m) v.append(i);
else t[r].append(i);
}
for(auto & i : v){
p = a[i], q = b[i];
xy[c[i]][p + q].erase(q);
yx[c[i]][p - q].erase(p);
x[c[i]][q & 1][p].erase(q);
y[c[i]][p & 1][q].erase(p);
}
t.erase(m);
v.clear();
}
for(auto & i : t[1e9 + 1])
cout << i << nl;
}
int terminator(){
L0TA;
solve();
return 0;
}
