#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int N;
cin >> N;
map<char, int> mp = {{'E', 0}, {'S', 1}, {'W', 2}, {'N', 3}};
vector<array<int, 3>> a(N);
for (int i = 0; i < N; ++i) {
cin >> a[i][0] >> a[i][1];
char c;
cin >> c;
int id = mp[c];
a[i][2] = id;
}
priority_queue<array<int, 3>> pq;
vector<map<int, set<array<int, 2>>>> pos(4), neg(4), line(4);
for (int i = 0; i < N; ++i) {
if (a[i][2] % 2 == 0) line[a[i][2]][a[i][1]].insert({a[i][0], i});
else line[a[i][2]][a[i][0]].insert({a[i][1], i});
pos[a[i][2]][a[i][0] + a[i][1]].insert({a[i][0], i});
neg[a[i][2]][a[i][0] - a[i][1]].insert({a[i][0], i});
}
auto calc = [&](int i, int j) -> int {
int sum = abs(a[i][0] - a[j][0]) + abs(a[i][1] - a[j][1]);
assert(sum % 2 == 0);
assert(sum > 0);
return sum / 2;
};
set<int> deleted;
vector<char> C = {'E', 'S', 'W', 'N'};
set<string> st;
for (char c : C) {
for (char ci : C) {
if (c == ci) continue;
string s = ""; s += c; s += ci;
st.insert(s);
}
}
auto dbg = [&](int i, int j) -> void {
int x1 = a[i][0], y1 = a[i][1], x2 = a[j][0], y2 = a[j][1];
string s = ""; s += C[a[i][2]]; s += C[a[j][2]];
if (!st.count(s)) {
cerr << "Trying to match an impossible case: " << s << "\n";
assert(false);
}
if (abs(a[i][2] - a[j][2]) % 2 == 0) {
if (a[i][2] == 0 || a[j][2] == 0) {
if (y1 != y2) {
cerr << "Wrong matching for a line " << i + 1 << " " << j + 1 << "!\n";
assert(false);
}
} else if (a[i][2] == 1 || a[j][2] == 1) {
if (x1 != x2) {
cerr << "Wrong matching for a line " << i + 1 << " " << j + 1 << "!\n";
assert(false);
}
}
return;
}
int k1 = abs(x1 - x2);
int k2 = abs(y1 - y2);
cerr << k1 << " " << k2 << "\n";
if (k1 != k2) {
cerr << "Incorrect matching at " << i + 1 << " " << j + 1 << "!\n";
assert(false);
}
};
cerr << "neg:\n";
for (int i = 0; i < 4; ++i) {
cerr << i << ":\n";
for (auto u : neg[i]) {
cerr << u.first << " = \n";
for (auto v : u.second) {
cerr << "( " << a[v[1]][0] << " , " << a[v[1]][1] << " )\n";
}
cerr << "\n";
}
}
cerr << "pos:\n";
for (int i = 0; i < 4; ++i) {
cerr << i << ":\n";
for (auto u : pos[i]) {
cerr << u.first << " = \n";
for (auto v : u.second) {
cerr << "( " << a[v[1]][0] << " , " << a[v[1]][1] << " )\n";
}
cerr << "\n";
}
}
cerr << "line: \n";
for (int i = 0; i < 4; ++i) {
cerr << i << ":\n";
for (auto u : line[i]) {
cerr << u.first << " = \n";
for (auto v : u.second) {
cerr << "( " << a[v[1]][0] << " , " << a[v[1]][1] << " )\n";
}
cerr << "\n";
}
}
auto pushit = [&](auto& M, int x, int k, bool up, int i, string name_of_bucket) -> void {
cerr << "Lookup in " << name_of_bucket
<< " for key="<< k
<< " → found? " << (M.count(k) ? "true!" : "false...") << "\n";
if (!M.count(k)) return;
set<array<int, 2>>& v = M[k];
auto it = v.lower_bound({x, -1});
if (up) {
if (it == end(v)) return;
if ((*it)[0] == x) {
++it;
if (it == end(v)) return;
}
} else {
if ((*it)[0] == x) {
if (it == begin(v)) return;
it--;
}
}
int j = (*it)[1];
int t = calc(i, j);
assert(!deleted.count(j));
dbg(i, j);
pq.push({-t, i, j});
};
auto add = [&](int i) -> void {
int x = a[i][0];
int y = a[i][1];
if (a[i][2] == 0) {
pushit(neg[3], x, x - y, true, i, "neg 3");
pushit(pos[1], x, x + y, true, i, "pos 1");
pushit(line[2], x, y, true, i, "line 2");
}
if (a[i][2] == 2) {
pushit(neg[1], x, x - y, false, i, "neg 1");
pushit(pos[3], x, x + y, false, i, "pos 3");
pushit(line[0], x, y, false, i, "line 0");
}
if (a[i][2] == 1) {
pushit(neg[2], x, x - y, false, i, "neg 2");
pushit(pos[0], x, x + y, true, i, "pos 0");
pushit(line[3], y, x, true, i, "line 3");
}
if (a[i][2] == 3) {
pushit(neg[0], x, x - y, true, i, "neg 2");
pushit(pos[2], x, x + y, false, i, "pos 0");
pushit(line[1], y, x, false, i, "line 1");
}
};
for (int i = 0; i < N; ++i) {
// cerr << i << "\n";
add(i);
}
vector<int> todelete, tocalc;
auto get_unique = [&](vector<int>& v) -> void {
sort(begin(v), end(v));
v.erase(unique(begin(v), end(v)), end(v));
};
auto rem = [&](int i) -> void {
// line[a[i][2]][a[i][1]].insert({a[i][0], i});
if (a[i][2] % 2 == 0) assert(line[a[i][2]][a[i][1]].erase({a[i][0], i}));
else assert(line[a[i][2]][a[i][0]].erase({a[i][1], i}));
assert(pos[a[i][2]][a[i][0] + a[i][1]].erase({a[i][0], i}));
assert(neg[a[i][2]][a[i][0] - a[i][1]].erase({a[i][0], i}));
};
// cerr << pq.size() << endl;
while (pq.size()) {
int d = -pq.top()[0];
while (pq.size() && d == -pq.top()[0]) {
int i = pq.top()[1];
int j = pq.top()[2];
pq.pop();
int fi = deleted.count(i);
int fj = deleted.count(j);
cerr << i + 1 << " " << j + 1 << " " << fi << " " << fj << endl;
if (fi && fj) continue;
if (fi && !fj) tocalc.push_back(j);
else if (!fi && fj) tocalc.push_back(i);
else {
assert(!fi && !fj);
todelete.push_back(i);
todelete.push_back(j);
}
}
get_unique(todelete);
get_unique(tocalc);
while (todelete.size()) {
int v = todelete.back();
todelete.pop_back();
// cout << v << " ";
assert(!deleted.count(v));
rem(v);
deleted.insert(v);
}
// cout << "\n";
while (tocalc.size()) {
int v = tocalc.back();
tocalc.pop_back();
add(v);
}
}
for (int i = 0; i < N; ++i) {
if (!deleted.count(i)) {
cout << i + 1 << "\n";
}
}
}
