#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
#define ll long long
#define pii pair<ll,ll>
#define fi first
#define sec second
#define ld long double
ostream& operator << (ostream& os, pii x){
os << "[";
os << " " << x.fi << " " << x.sec;
os << " ]";
return os;
}
ostream& operator << (ostream& os, pair<pii, ll> x){
os << "[";
os << " " << x.fi << " " << x.sec;
os << " ]";
return os;
}
ostream& operator << (ostream& os, pair<ll, pii> x){
os << "[";
os << " " << x.fi << " " << x.sec;
os << " ]";
return os;
}
template <typename T>
ostream& operator << (ostream& os, vector<T>tmp){
os << "[";
for(auto x : tmp) os << " " << x;
os << " ]";
return os;
}
template <typename T>
ostream& operator << (ostream& os, set<T>tmp){
os << "[";
for(auto x : tmp) os << " " << x;
os << " ]";
return os;
}
template <typename T>
ostream& operator << (ostream& os, multiset<T>tmp){
os << "[";
for(auto x : tmp) os << " " << x;
os << " ]";
return os;
}
const ll MOD = 998244353;
const ll N = 2e5;
const ll INF = 2e18;
// modulo operations
void add(ll &a, ll b) { a = (a + b) % MOD; }
void sub(ll &a, ll b) { a -= b; while(a < 0) a += MOD; a %= MOD; }
void mul(ll &a, ll b) { a = (a * b) % MOD; }
ll expo(ll a, ll b) {
ll ans = 1;
while(b > 0){
if(b & 1) mul(ans, a);
mul(a, a);
b /= 2;
}
return ans;
}
ll x[N + 5], y[N + 5];
char d[N + 5];
int32_t main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int tc = 1;
// cin >> tc;
for(;tc--;){
ll n; cin >> n;
for(int i = 1; i <= n; i++) cin >> x[i] >> y[i] >> d[i];
auto conv = [&](char cur){
if(cur == 'N') return 0;
if(cur == 'S') return 1;
if(cur == 'W') return 2;
if(cur == 'E') return 3;
};
map<ll, set<pii>> sub[4], plus[4], hori[4], verti[4];
map<pii, char> dir;
map<pii, ll> id;
auto dist = [&](pii a, pii b){
return abs(a.fi - b.fi) + abs(a.sec - b.sec);
};
priority_queue<pair<ll, pair<pii, pii>>> pq;
auto upd = [&](pii a){
char cur = dir[a];
ll Y = a.fi, X = a.sec;
if(cur == 'N'){
auto cur = verti[conv('S')][X].lower_bound({Y, X});
if(cur != verti[conv('S')][X].begin() && !verti[conv('S')][X].empty()){
--cur;
ll cost = dist({Y, X}, *(cur));
pq.push({-cost, {{Y, X}, *(cur)}});
}
cur = plus[conv('E')][X + Y].lower_bound({Y, X});
if(cur != plus[conv('E')][X + Y].begin() && !plus[conv('E')][X + Y].empty()){
--cur;
ll cost = dist({Y, X}, *(cur));
pq.push({-cost, {{Y, X}, *(cur)}});
}
cur = sub[conv('W')][X - Y].lower_bound({Y, X});
if(cur != sub[conv('W')][X - Y].begin() && !sub[conv('W')][X - Y].empty()){
--cur;
ll cost = dist({Y, X}, *(cur));
pq.push({-cost, {{Y, X}, *(cur)}});
}
}
if(cur == 'S'){
auto cur = verti[conv('N')][X].upper_bound({Y, X});
if(cur != verti[conv('N')][X].end() && !verti[conv('N')][X].empty()){
ll cost = dist({Y, X}, *(cur));
pq.push({-cost, {{Y, X}, *(cur)}});
}
cur = plus[conv('E')][X + Y].upper_bound({Y, X});
if(cur != plus[conv('E')][X + Y].end() && !plus[conv('E')][X + Y].empty()){
ll cost = dist({Y, X}, *(cur));
pq.push({-cost, {{Y, X}, *(cur)}});
}
cur = sub[conv('W')][X - Y].upper_bound({Y, X});
if(cur != sub[conv('W')][X - Y].end() && !sub[conv('W')][X - Y].empty()){
ll cost = dist({Y, X}, *(cur));
pq.push({-cost, {{Y, X}, *(cur)}});
}
}
if(cur == 'W'){
auto cur = hori[conv('E')][Y].lower_bound({Y, X});
if(cur != verti[conv('E')][Y].begin() && !verti[conv('E')][Y].empty()){
--cur;
ll cost = dist({Y, X}, *(cur));
pq.push({-cost, {{Y, X}, *(cur)}});
}
cur = sub[conv('S')][X - Y].lower_bound({Y, X});
if(cur != sub[conv('S')][X - Y].begin() && !sub[conv('S')][X - Y].empty()){
--cur;
ll cost = dist({Y, X}, *(cur));
pq.push({-cost, {{Y, X}, *(cur)}});
}
cur = plus[conv('N')][X + Y].upper_bound({Y, X});
if(cur != plus[conv('N')][X + Y].end() && !plus[conv('N')][X + Y].empty()){
ll cost = dist({Y, X}, *(cur));
pq.push({-cost, {{Y, X}, *(cur)}});
}
}
if(cur == 'E'){
auto cur = hori[conv('W')][Y].upper_bound({Y, X});
if(cur != hori[conv('W')][Y].end() && !hori[conv('W')][Y].empty()){
ll cost = dist({Y, X}, *(cur));
pq.push({-cost, {{Y, X}, *(cur)}});
}
cur = sub[conv('N')][X - Y].upper_bound({Y, X});
if(cur != sub[conv('N')][X - Y].end() && !sub[conv('N')][X - Y].empty()){
ll cost = dist({Y, X}, *(cur));
pq.push({-cost, {{Y, X}, *(cur)}});
}
cur = plus[conv('S')][X + Y].lower_bound({Y, X});
if(cur != plus[conv('S')][X + Y].begin() && !plus[conv('S')][X + Y].empty()){
--cur;
ll cost = dist({Y, X}, *(cur));
pq.push({-cost, {{Y, X}, *(cur)}});
}
}
};
auto ins = [&](pii a){
ll Y = a.fi, X = a.sec;
char cur = dir[a];
sub[conv(cur)][X - Y].insert({Y, X});
plus[conv(cur)][X + Y].insert({Y, X});
hori[conv(cur)][Y].insert({Y, X});
verti[conv(cur)][X].insert({Y, X});
};
map<pii, bool> vis;
auto del = [&](pii a){
if(vis[a]) return;
vis[a] = 1;
ll Y = a.fi, X = a.sec;
char cur = dir[a];
sub[conv(cur)][X - Y].erase({Y, X});
plus[conv(cur)][X + Y].erase({Y, X});
hori[conv(cur)][Y].erase({Y, X});
verti[conv(cur)][X].erase({Y, X});
};
for(int i = 1; i <= n; i++){
id[{y[i], x[i]}] = i;
dir[{y[i], x[i]}] = d[i];
ins({y[i], x[i]});
}
// generate
map<pii, ll> dp;
for(int i = 1; i <= n; i++){
upd({y[i], x[i]});
// cout << y[i] << " " << x[i] << "\n";
dp[{y[i], x[i]}] = INF;
}
for(;!pq.empty();){
auto [cost, A] = pq.top(); pq.pop();
cost *= -1;
if(dp[A.fi] >= cost && dp[A.sec] >= cost){
dp[A.fi] = cost, dp[A.sec] = cost;
continue;
}
else{
if(dp[A.fi] >= cost) upd(A.fi);
else del(A.fi);
if(dp[A.sec] >= cost) upd(A.sec);
else del(A.sec);
}
}
vector<ll> v;
for(auto &[now, time] : dp){
if(time == INF){
v.push_back(id[now]);
}
}
for(auto &x : v) cout << x << "\n";
}
}
/*
*/
