#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;
}
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]}
// });
// }
// }
// }
// }
// }
map<int, int> group_cnt;
for (int i = 0; i < n; i++) {
int x = a[i].X.X;
int y = a[i].X.Y;
int g = x + y;
group_cnt[g]++;
}
map<int, vec<int>> groups;
for (auto [g, cnt]: group_cnt) {
groups[g].reserve(cnt);
}
for (int i = 0; i < n; i++) {
int x = a[i].X.X;
int y = a[i].X.Y;
int g = x + y;
groups[g].push_back(i);
}
const pii E = {1, 0};
const pii S = {0, 1};
vec<bool> hit(n, false);
for (auto [g, v]: groups) {
int m = v.size();
vec<tuple<pii, pii, int>> data;
for (int i = 0; i < m; i++) {
int idx = v[i];
auto pos = a[idx].X;
auto dir = a[idx].Y;
data.push_back({pos, dir, idx});
// cerr << g << ": " << idx + 1 << " " << pos << " " << dir << endl;
}
sort(all(data));
stack<int> easts;
for (auto [pos, dir, idx]: data) {
if (dir == E) {
easts.push(idx);
} else {
if (easts.empty()) {
continue;
} else {
int last = easts.top();
easts.pop();
hit[last] = true;
hit[idx] = true;
}
}
}
}
for (int i = 0; i < n; i++) {
if (!hit[i]) {
cout << i + 1 << endl;
return 0;
}
}
}
