#include "bits/stdc++.h"
#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;
}
signed main() {
int n; cin >> n;
vec<pair<pii, pii>> a(n);
for (int i = 0; i < n; i++) {
int x, y;
char c;
cin >> x >> y >> c;
pii dir;
if (c == 'N') dir = { 0, -1};
if (c == 'S') dir = { 0, 1};
if (c == 'E') dir = { 1, 0};
if (c == 'W') dir = {-1, 0};
a[i] = {{x, y}, dir};
}
map<int, vec<int>> y_diag, x_diag, x_line, y_line;
for (int i = 0; i < n; i++) {
int x_int = abs(x_intercept(a[i].X));
int y_int = abs(y_intercept(a[i].X));
int x = a[i].X.X;
int y = a[i].X.Y;
x_diag[x_int].push_back(i);
y_diag[y_int].push_back(i);
x_line[x].push_back(i);
y_line[y].push_back(i);
// cerr << i + 1 << " " << x << " " << y << " " << x_int << " " << y_int << endl;
}
vec<pair<int, pair<int, int>>> pairs;
for (auto &group: {x_line, y_line, x_diag, y_diag}) {
for (auto &[_, v]: group) {
for (int i = 0; i < v.size(); i++) {
for (int j = i + 1; j < v.size(); j++) {
int time = collide(a[v[i]], a[v[j]]);
if (time != INT_MAX) {
pairs.push_back({
time,
{v[i], v[j]}
});
}
}
}
}
}
vec<int> hit(n, INT_MAX);
sort(all(pairs));
for (auto [time, p]: pairs) {
int i = p.X, j = p.Y;
if (hit[i] < time || hit[j] < time) continue;
hit[i] = hit[j] = time;
}
for (int i = 0; i < n; i++) {
// cerr << i + 1 << " " << hit[i] << endl;
if (hit[i] == INT_MAX) {
cout << i + 1 << "\n";
}
}
}
