// absolutely incredible
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define REP(i, a, b) for(int i = a; i >= b; --i)
#define pb push_back
#define left _________left
#define right _________right
#define NAME ""
const int mod = 1e9 + 7;
bool maximize(int &u, int v){
if(v > u){
u = v;
return true;
}
return false;
}
bool minimize(int &u, int v){
if(v < u){
u = v;
return true;
}
return false;
}
bool maximizell(long long &u, long long v){
if(v > u){
u = v;
return true;
}
return false;
}
bool minimizell(long long &u, long long v){
if(v < u){
u = v;
return true;
}
return false;
}
int fastPow(int a, int n){
if(n == 0) return 1;
int t = fastPow(a, n >> 1);
t = 1ll * t * t % mod;
if(n & 1) t = 1ll * t * a % mod;
return t;
}
void add(int &u, int v){
u += v;
if(u >= mod) u -= mod;
}
void sub(int &u, int v){
u -= v;
if(u < 0) u += mod;
}
const int maxN = 2e5 + 5;
struct Point{
int x, y;
char d;
int intersect(const Point &rhs)const{
if(d == rhs.d) return 0;
int temp = abs(x - rhs.x) + abs(y - rhs.y);
temp >>= 1;
if(d == 'N'){
if(rhs.d == 'E'){
if(y - temp == rhs.y && rhs.x + temp == x) return temp;
return 0;
}
if(rhs.d == 'S'){
if(y - temp == rhs.y + temp && x == rhs.x) return temp;
return 0;
}
if(y - temp == rhs.y && x == rhs.x - temp) return temp;
return 0;
}
if(d == 'E'){
if(rhs.d == 'N'){
if(x + temp == rhs.x && rhs.y - temp == y) return temp;
return 0;
}
if(rhs.d == 'W'){
if(x + temp == rhs.x - temp && y == rhs.y) return temp;
return 0;
}
if(x + temp == rhs.x && rhs.y + temp == y) return temp;
return 0;
}
if(d == 'S'){
if(rhs.d == 'N'){
if(y + temp == rhs.y - temp && x == rhs.x) return temp;
return 0;
}
if(rhs.d == 'E'){
if(y + temp == rhs.y && rhs.x + temp == x) return temp;
return 0;
}
if(y + temp == rhs.y && rhs.x - temp == x) return temp;
return 0;
}
if(rhs.d == 'N'){
if(x - temp == rhs.x && rhs.y - temp == y) return temp;
return 0;
}
if(rhs.d == 'E'){
if(x - temp == rhs.x + temp && y == rhs.y) return temp;
return 0;
}
if(x - temp == rhs.x && rhs.y + temp == y) return temp;
return 0;
}
}p[maxN];
const int INF = INT_MAX;
int N;
namespace subtask12345{
bool check(){
return N <= 5000;
}
const int maxT = 12497500 + 1;
pair<int, pair<int, int>> t[maxT];
int del[maxN];
void solve(){
int cnt = 0;
FOR(i, 1, N){
FOR(j, i + 1, N){
int k = p[i].intersect(p[j]);
if(k > 0)t[++cnt] = {k, {i, j}};
}
}
sort(t + 1, t + 1 + cnt);
FOR(i, 1, N)del[i] = INF;
FOR(i, 1, cnt){
int k = t[i].first;
int pi = t[i].second.first;
int pj = t[i].second.second;
if(del[pi] < k || del[pj] < k)continue;
del[pi] = del[pj] = k;
}
FOR(i, 1, N){
if(del[i] == INF)cout << i << "\n";
}
}
}
namespace subtask6{
vector<pair<pair<int, int>, int>> v[maxN];
int comp[maxN];
bool check(){
FOR(i, 1, N){
if(p[i].d == 'S' || p[i].d == 'E') continue;
return false;
}
return true;
}
bool del[maxN];
void solve(){
FOR(i, 1, N){
comp[i] = p[i].x + p[i].y;
}
sort(comp + 1, comp + 1 + N);
FOR(i, 1, N){
int x = lower_bound(comp + 1, comp + 1 + N, p[i].x + p[i].y) - comp;
v[x].push_back({{p[i].x, p[i].y}, i});
}
stack<int> st;
FOR(i, 1, N){
sort(v[i].begin(), v[i].end());
while(st.size())st.pop();
for(pair<pair<int, int>, int> x : v[i]){
if(p[x.second].d == 'E')st.push(x.second);
else{
if(!st.empty()){
del[st.top()] = del[x.second] = true;
st.pop();
}
}
}
}
FOR(i, 1, N){
if(del[i] == false)cout << i << "\n";
}
}
}
namespace subtask7{
int md[maxN], sd[maxN], hor[maxN], ver[maxN];
int del[maxN];
priority_queue<tuple<int, int, int, int, int>, vector<tuple<int, int, int, int, int>>, greater<tuple<int, int, int, int, int>>> Q;
int nxt[3][maxN];
vector<int> v[maxN];
bool sX(const int &a, const int &b){
return p[a].x < p[b].x;
}
bool gX(const int &a, const int &b){
return p[a].x > p[b].x;
}
bool Y(const int &a, const int &b){
return p[a].y < p[b].y;
}
const int INF = 1e9;
int val[4][maxN];
void make_List(char d1, char d2, int type, bool dig){
FOR(i, 1, N)v[i].clear();
FOR(i, 1, N){
if(p[i].d != d1 && p[i].d != d2)continue;
v[val[type][i]].push_back(i);
}
stack<int> st;
bool sortx = false;
int dir1, dir2;
if(dig){
dir1 = 0;
dir2 = 2;
}else dir1 = dir2 = 1;
if(d1 == 'S' && d2 == 'W')sortx = true;
else if(d1 == 'W' && d2 == 'N') sortx = false;
else if(d1 == 'N' && d2 == 'E') sortx = false;
else if(d1 == 'E' && d2 == 'S') sortx = true;
else if(d1 == 'E' && d2 == 'W')sortx = true;
FOR(i, 1, N){
if(sortx)sort(v[i].begin(), v[i].end(), sX);
else if(dig) sort(v[i].begin(), v[i].end(), gX);
else sort(v[i].begin(), v[i].end(), Y);
while(!st.empty()) st.pop();
for(int id : v[i]){
if(p[id].d == d1)st.push(id);
else{
if(!st.empty()){
int tp = st.top();
st.pop();
Q.push({p[id].intersect(p[tp]), tp, id, dir1, dir2});
}
}
}
if(dig){
int lastF = 0, lastS = 0;
for(int j = 0; j < v[i].size(); ++j){
int id = v[i][j];
if(p[id].d == d2)continue;
nxt[0][id] = lastF;
lastF = id;
}
for(int j = v[i].size() - 1; j >= 0; --j){
int id = v[i][j];
if(p[id].d == d1)continue;
nxt[2][id] = lastS;
lastS = id;
}
continue;
}else{
int lastF = 0, lastS = 0;
for(int j = 0; j < v[i].size(); ++j){
int id = v[i][j];
if(p[id].d == d2)continue;
nxt[1][id] = lastF;
lastF = id;
}
for(int j = v[i].size() - 1; j >= 0; --j){
int id = v[i][j];
if(p[id].d == d1)continue;
nxt[1][id] = lastS;
lastS = id;
}
}
}
}
void solve(){
FOR(i, 1, N){
md[i] = p[i].x - p[i].y;
sd[i] = p[i].x + p[i].y;
hor[i] = p[i].y;
ver[i] = p[i].x;
}
sort(md + 1, md + 1 + N);
sort(sd + 1, sd + 1 + N);
sort(hor + 1, hor + 1 + N);
sort(ver + 1, ver + 1 + N);
FOR(i, 1, N){
val[0][i] = lower_bound(md + 1, md + 1 + N, p[i].x - p[i].y) - md;
val[1][i] = lower_bound(sd + 1, sd + 1 + N, p[i].x + p[i].y) - sd;
val[2][i] = lower_bound(hor + 1, hor + 1 + N, p[i].y) - hor;
val[3][i] = lower_bound(ver + 1, ver + 1 + N, p[i].x) - ver;
}
make_List('S', 'W', 0, true);
make_List('W', 'N', 1, true);
make_List('N', 'E', 0, true);
make_List('E', 'S', 1, true);
make_List('E', 'W', 2, false);
make_List('S', 'N', 3, false);
FOR(i, 1, N)del[i] = INF;
del[0] = INF;
while(!Q.empty()){
auto[k, f, s, dir1, dir2] = Q.top();
Q.pop();
if(del[f] <= k && del[s] <= k)continue;
if(del[f] == k){
assert(del[s] == INF);
del[s] = k;
continue;
}
if(del[s] == k){
assert(del[f] == INF);
del[f] = k;
continue;
}
if(del[f] < k){
assert(del[s] == INF);
int F = f;
while(del[f] != INF) f = nxt[dir1][f];
nxt[dir1][F] = f;
if(f) Q.push({p[s].intersect(p[f]), f, s, dir1, dir2});
continue;
}
if(del[s] < k){
assert(del[f] == INF);
int S = s;
while(del[s] != INF) s = nxt[dir2][s];
nxt[dir2][S] = s;
if(s) Q.push({p[f].intersect(p[s]), f, s, dir1, dir2});
continue;
}
del[f] = del[s] = k;
}
FOR(i, 1, N){
if(del[i] == INF)cout << i << '\n';
}
}
}
void solve(){
cin >> N;
int x, y;
char d;
FOR(i, 1, N){
cin >> x >> y >> d;
p[i] = {x, y, d};
}
// if(subtask12345 :: check()) return subtask12345 :: solve();
// if(subtask6 :: check()) return subtask6 :: solve();
return subtask7 :: solve();
}
int main(){
if(fopen(NAME".inp", "r")){
freopen(NAME".inp", "r", stdin);
freopen(NAME".out", "w", stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
while(t--){
solve();
}
return 0;
}
