#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;
}
vector<map<int, set<array<int, 2>>>> coord(4);
for (int i = 0; i < N; ++i) {
if (a[i][2] != 1 && a[i][2] != 2) {
coord[a[i][2]][a[i][0] + a[i][1]].insert({a[i][0], i});
}
}
priority_queue<array<int, 3>> pq;
for (int i = 0; i < N; ++i) {
if (a[i][2] == 1) {
set<array<int, 2>>& c = coord[0][a[i][0] + a[i][1]];
auto it = c.upper_bound({a[i][0], -1});
if (it != c.begin()) {
--it;
int tim = a[i][0] - (*it)[0];
assert(tim > 0);
pq.push({-tim, i, (*it)[1]});
}
} else if (a[i][2] == 2) {
set<array<int, 2>>& c = coord[3][a[i][0] + a[i][1]];
auto it = c.upper_bound({a[i][0], -1});
if (it != c.begin()) {
--it;
int tim = a[i][0] - (*it)[0];
assert(tim > 0);
pq.push({-tim, i, (*it)[1]});
}
}
}
for (int i = 0; i < 4; ++i) coord[i].clear();
for (int i = 0; i < N; ++i) {
if (a[i][2] != 3 && a[i][2] != 2) {
coord[a[i][2]][a[i][0] - a[i][1]].insert({a[i][0], i});
}
}
for (int i = 0; i < N; ++i) {
if (a[i][2] == 3) {
set<array<int, 2>>& c = coord[0][a[i][0] - a[i][1]];
auto it = c.upper_bound({a[i][0], -1});
if (it != c.begin()) {
--it;
int tim = a[i][0] - (*it)[0];
assert(tim > 0);
pq.push({-tim, i, (*it)[1]});
}
} else if (a[i][2] == 2) {
set<array<int, 2>>& c = coord[1][a[i][0] - a[i][1]];
auto it = c.upper_bound({a[i][0], -1});
if (it != c.begin()) {
--it;
int tim = a[i][0] - (*it)[0];
assert(tim > 0);
pq.push({-tim, i, (*it)[1]});
}
}
}
for (int i = 0; i < 4; ++i) coord[i].clear();
for (int i = 0; i < N; ++i) {
if (a[i][2] != 3 && a[i][2] != 2) {
if (a[i][2] == 0) coord[a[i][2]][a[i][1]].insert({a[i][0], i});
else coord[a[i][2]][a[i][0]].insert({a[i][1], i});
}
}
for (int i = 0; i < N; ++i) {
if (a[i][2] == 3) {
set<array<int, 2>>& c = coord[1][a[i][0]];
auto it = c.upper_bound({a[i][1], -1});
if (it != c.end()) {
int tim = -a[i][1] + (*it)[0];
assert(tim > 0 && tim % 2 == 0);
tim /= 2;
pq.push({-tim, i, (*it)[1]});
}
} else if (a[i][2] == 2) {
set<array<int, 2>>& c = coord[1][a[i][1]];
auto it = c.upper_bound({a[i][0], -1});
if (it != c.begin()) {
--it;
int tim = a[i][0] - (*it)[0];
assert(tim > 0);
assert(tim % 2 == 0);
tim /= 2;
pq.push({-tim, i, (*it)[1]});
}
}
}
for (int i = 0; i < 4; ++i) coord[i].clear();
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 del = [&](int i) -> void {
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}));
};
auto ins = [&](int i) -> void {
if (a[i][2] == 0) {
auto& c = line[2][a[i][1]];
auto it = c.upper_bound({a[i][0], -1});
if (it != c.end()) {
int tim = -a[i][0] + (*it)[0];
assert(tim > 0 && tim % 2 == 0);
tim /= 2;
pq.push({-tim, i, (*it)[1]});
}
auto& c1 = pos[1][a[i][0] + a[i][1]];
auto it1 = c1.upper_bound({a[i][0], -1});
if (it1 != c1.end()) {
int tim = -a[i][0] + (*it1)[0];
assert(tim > 0);
pq.push({-tim, i, (*it1)[1]});
}
auto& c2 = neg[3][a[i][0] - a[i][1]];
auto it2 = c2.upper_bound({a[i][0], -1});
if (it2 != c2.end()) {
int tim = -a[i][0] + (*it2)[0];
assert(tim > 0);
pq.push({-tim, i, (*it2)[1]});
}
} else if (a[i][2] == 1) {
auto& c = line[3][a[i][0]];
auto it = c.upper_bound({a[i][1], -1});
if (it != c.begin()) {
it--;
int tim = a[i][1] - (*it)[0];
assert(tim > 0 && tim % 2 == 0);
tim /= 2;
pq.push({-tim, i, (*it)[1]});
}
auto& c1 = pos[0][a[i][0] + a[i][1]];
auto it1 = c1.upper_bound({a[i][0], -1});
if (it1 != c1.begin()) {
it1--;
int tim = a[i][0] - (*it1)[0];
assert(tim > 0);
pq.push({-tim, i, (*it1)[1]});
}
auto& c2 = neg[2][a[i][0] - a[i][1]];
auto it2 = c2.upper_bound({a[i][0], -1});
if (it2 != c2.end()) {
int tim = -a[i][0] + (*it2)[0];
assert(tim > 0);
pq.push({-tim, i, (*it2)[1]});
}
} else if (a[i][2] == 2) {
auto& c = line[0][a[i][1]];
auto it = c.upper_bound({a[i][0], -1});
if (it != c.begin()) {
it--;
int tim = a[i][0] - (*it)[0];
assert(tim > 0 && tim % 2 == 0);
tim /= 2;
pq.push({-tim, i, (*it)[1]});
}
auto& c1 = pos[3][a[i][0] + a[i][1]];
auto it1 = c1.upper_bound({a[i][0], -1});
if (it1 != c1.begin()) {
it1--;
int tim = a[i][0] - (*it1)[0];
assert(tim > 0);
pq.push({-tim, i, (*it1)[1]});
}
auto& c2 = neg[1][a[i][0] - a[i][1]];
auto it2 = c2.upper_bound({a[i][0], -1});
if (it2 != c2.begin()) {
it2--;
int tim = a[i][0] - (*it2)[0];
assert(tim > 0);
pq.push({-tim, i, (*it2)[1]});
}
} else {
auto& c = line[1][a[i][0]];
auto it = c.upper_bound({a[i][1], -1});
if (it != c.end()) {
int tim = -a[i][1] + (*it)[0];
assert(tim > 0 && tim % 2 == 0);
tim /= 2;
pq.push({-tim, i, (*it)[1]});
}
auto& c1 = pos[2][a[i][0] + a[i][1]];
auto it1 = c1.upper_bound({a[i][0], -1});
if (it1 != c1.end()) {
int tim = -a[i][0] + (*it1)[0];
assert(tim > 0);
pq.push({-tim, i, (*it1)[1]});
}
auto& c2 = neg[0][a[i][0] - a[i][1]];
auto it2 = c2.upper_bound({a[i][0], -1});
if (it2 != c2.begin()) {
it2--;
int tim = -a[i][0] + (*it2)[0];
assert(tim > 0);
pq.push({-tim, i, (*it2)[1]});
}
}
};
int timer = 1;
// auto nq = pq;
// while (nq.size()) {
// cout << -nq.top()[0] << " " << nq.top()[1] + 1 << " " << nq.top()[2] + 1 << "\n";
// nq.pop();
// }
// ofstream cout("out.txt");
unordered_set<int> deleted;
while (pq.size()) {
int d = -pq.top()[0];
vector<int> recalc;
vector<int> todel;
while (pq.size() && -pq.top()[0] == d) {
int i = pq.top()[1];
int j = pq.top()[2];
pq.pop();
// cout << d << " = " << i + 1 << " " << j + 1 << " = " << deleted.count(i) << " " << deleted.count(j) << "\n";
// if (i + 1 == 70 && j + 1 == 1) break;
// if (deleted.count(i) || deleted.count(j)) continue;
if (deleted.count(i) && !deleted.count(j)) recalc.push_back(j);
else if (deleted.count(j) && !deleted.count(i)) recalc.push_back(i);
else if (!deleted.count(j) && !deleted.count(i)) {
todel.push_back(i);
todel.push_back(j);
}
}
sort(begin(todel), end(todel));
todel.erase(unique(begin(todel), end(todel)), end(todel));
for (auto& u : todel) {
del(u);
deleted.insert(u);
}
// cout << pq.size() << " -> ";
for (auto& u : recalc) {
ins(u);
}
// cout << pq.size() << "\n";
// cout << "end\n";
}
for (int i = 0; i < N; ++i) {
if (!deleted.count(i)) {
cout << i + 1 << "\n";
}
}
}
