#include "bits/stdc++.h"
#include <algorithm>
#include <ostream>
using namespace std;
#define int long long
#define vec vector
#define all(x) (x).begin(), (x).end()
#define X first
#define Y second
using pii = pair<int, int>;
pii operator+(const pii &a, const pii &b) {
return {a.X + b.X, a.Y + b.Y};
}
pii operator-(const pii &a, const pii &b) {
return {a.X - b.X, a.Y - b.Y};
}
pii operator*(const pii &a, const int &b) {
return {a.X * b, a.Y * b};
}
pii operator-(const pii &a) {
return {-a.X, -a.Y};
}
int xdist(const pii &a, const pii &b) {
return abs(a.X - b.X);
}
int ydist(const pii &a, const pii &b) {
return abs(a.Y - b.Y);
}
int x_intercept(const pii &a) {
return a.X + a.Y;
}
int y_intercept(const pii &a) {
return a.X - a.Y;
}
ostream &operator<<(ostream &os, const pii &p) {
os << "(" << p.X << ", " << p.Y << ")";
return os;
}
int collide(pair<pii, pii> a, pair<pii, pii> b) {
auto posa = a.X;
auto posb = b.X;
auto dira = a.Y;
auto dirb = b.Y;
int disty = ydist(posa, posb);
int distx = xdist(posa, posb);
if (dira == dirb) return INT_MAX;
if (dira == -dirb) {
if (distx == 0 || disty == 0) {
int dist = max(distx, disty);
int time = dist / 2;
if (posa + dira * time == posb + dirb * time) {
return time;
}
}
return INT_MAX;
}
if (distx == disty) {
int dist = distx;
int time = dist;
if (posa + dira * time == posb + dirb * time) {
return time;
}
}
return INT_MAX;
}
vec<pair<pii, pii>> a;
const pii N = {0, -1};
const pii S = {0, 1};
const pii E = {1, 0};
const pii W = {-1, 0};
signed main() {
int n; cin >> n;
a.resize(n);
for (int i = 0; i < n; i++) {
int x, y;
char c;
cin >> x >> y >> c;
pii dir;
if (c == 'N') dir = N;
if (c == 'S') dir = S;
if (c == 'E') dir = E;
if (c == 'W') dir = W;
a[i] = {{x, y}, dir};
}
map<int, set<pii>> n_y_line, n_x_diag, n_y_diag,
s_y_line, s_x_diag, s_y_diag,
e_x_line, e_x_diag, e_y_diag,
w_x_line, w_x_diag, w_y_diag;
for(int i = 0; i < n; i++) {
auto pos = a[i].X;
auto dir = a[i].Y;
int x_int = x_intercept(pos);
int y_int = y_intercept(pos);
if (dir == N) {
n_y_line[pos.Y].insert(pos);
n_x_diag[x_int].insert(pos);
n_y_diag[y_int].insert(pos);
} else if (dir == S) {
s_y_line[pos.Y].insert(pos);
s_x_diag[x_int].insert(pos);
s_y_diag[y_int].insert(pos);
} else if (dir == E) {
e_x_line[pos.X].insert(pos);
e_x_diag[x_int].insert(pos);
e_y_diag[y_int].insert(pos);
} else if (dir == W) {
w_x_line[pos.X].insert(pos);
w_x_diag[x_int].insert(pos);
w_y_diag[y_int].insert(pos);
}
}
map<pii, int> removed_time;
for(int i = 0; i < n; i++) {
removed_time[a[i].X] = INT_MAX;
}
using collision = tuple<int, pair<pii, pii>, pair<pii, pii>>;
priority_queue<collision, vector<collision>, greater<collision>> pq;
auto add_collisions = [&](pii pos, pii dir) {
if (dir == E) {
auto s = s_x_diag[x_intercept(pos)].upper_bound(pos);
if (s != s_x_diag[x_intercept(pos)].end()) {
pq.push({collide({*s, S}, {pos, dir}), {pos, dir}, {*s, S}});
}
auto w = w_x_line[pos.X].upper_bound(pos);
if (w != w_x_line[pos.X].end()) {
pq.push({collide({*w, W}, {pos, dir}), {pos, dir}, {*w, W}});
}
auto n = n_y_diag[y_intercept(pos)].upper_bound(pos);
if (n != n_y_diag[y_intercept(pos)].end()) {
pq.push({collide({*n, N}, {pos, dir}), {pos, dir}, {*n, N}});
}
}
if (dir == S) {
auto e = e_y_diag[y_intercept(pos)].upper_bound(pos);
if (e != e_y_diag[y_intercept(pos)].begin()) {
e--;
pq.push({collide({*e, E}, {pos, dir}), {pos, dir}, {*e, E}});
}
auto n = n_y_line[pos.Y].upper_bound(pos);
if (n != n_y_line[pos.Y].end()) {
pq.push({collide({*n, N}, {pos, dir}), {pos, dir}, {*n, N}});
}
auto w = w_y_diag[y_intercept(pos)].upper_bound(pos);
if (w != w_y_diag[y_intercept(pos)].end()) {
pq.push({collide({*w, W}, {pos, dir}), {pos, dir}, {*w, W}});
}
}
if (dir == W) {
auto s = s_y_diag[y_intercept(pos)].upper_bound(pos);
if (s != s_y_diag[y_intercept(pos)].end()) {
pq.push({collide({*s, S}, {pos, dir}), {pos, dir}, {*s, S}});
}
auto e = e_x_line[pos.X].upper_bound(pos);
if (e != e_x_line[pos.X].begin()) {
e--;
pq.push({collide({*e, E}, {pos, dir}), {pos, dir}, {*e, E}});
}
auto n = n_y_line[pos.Y].upper_bound(pos);
if (n != n_y_line[pos.Y].begin()) {
n--;
pq.push({collide({*n, N}, {pos, dir}), {pos, dir}, {*n, N}});
}
}
if (dir == N) {
auto s = s_y_line[pos.Y].upper_bound(pos);
if (s != s_y_line[pos.Y].begin()) {
s--;
pq.push({collide({*s, S}, {pos, dir}), {pos, dir}, {*s, S}});
}
auto w = w_y_diag[y_intercept(pos)].upper_bound(pos);
if (w != w_y_diag[y_intercept(pos)].begin()) {
w--;
pq.push({collide({*w, W}, {pos, dir}), {pos, dir}, {*w, W}});
}
auto e = e_x_diag[x_intercept(pos)].upper_bound(pos);
if (e != e_x_diag[x_intercept(pos)].end()) {
e--;
pq.push({collide({*e, E}, {pos, dir}), {pos, dir}, {*e, E}});
}
}
};
for (int i = 0; i < n; i++) {
auto pos = a[i].X;
auto dir = a[i].Y;
add_collisions(pos, dir);
}
auto remove_point = [&](pii pos, pii dir) {
int x_int = x_intercept(pos);
int y_int = y_intercept(pos);
if (dir == N) {
n_y_line[pos.Y].erase(pos);
n_x_diag[x_int].erase(pos);
n_y_diag[y_int].erase(pos);
} else if (dir == S) {
s_y_line[pos.Y].erase(pos);
s_x_diag[x_int].erase(pos);
s_y_diag[y_int].erase(pos);
} else if (dir == E) {
e_x_line[pos.X].erase(pos);
e_x_diag[x_int].erase(pos);
e_y_diag[y_int].erase(pos);
} else if (dir == W) {
w_x_line[pos.X].erase(pos);
w_x_diag[x_int].erase(pos);
w_y_diag[y_int].erase(pos);
}
};
while(pq.size()) {
auto [time, p, q] = pq.top();
pq.pop();
// int p_seen = hits.count(p.X);
// int q_seen = hits.count(q.X);
// if (p_seen && q_seen) continue;
// if (p_seen || q_seen) {
// if (!p_seen) add_collisions(p.X, p.Y);
// if (!q_seen) add_collisions(q.X, q.Y);
// } else {
// hits.insert(p.X);
// hits.insert(q.X);
// remove_point(p.X, p.Y);
// remove_point(q.X, q.Y);
// }
//
int pt = removed_time[p.X];
int qt = removed_time[q.X];
if (pt < time || qt < time) {
if (pt == INT_MAX) add_collisions(p.X, p.Y);
if (qt == INT_MAX) add_collisions(q.X, q.Y);
} else {
removed_time[p.X] = time;
removed_time[q.X] = time;
remove_point(p.X, p.Y);
remove_point(q.X, q.Y);
}
}
for (int i = 0; i < n; i++) {
pii pos = a[i].X;
if (removed_time[pos] == INT_MAX) {
cout << i + 1 << "\n";
}
}
}
