#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
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;
a[i][2] = mp[c];
}
// Initial candidate collisions
vector<map<int, set<array<int, 2>>>> coord(4);
priority_queue<array<int,3>> pq;
auto add_initial = [&](int dir_filter, int lookup_dir) {
for (int i = 0; i < N; ++i) {
if (a[i][2] == dir_filter) {
auto& c = coord[lookup_dir][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]});
}
}
}
};
// Eastern vs others on x+y
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});
}
}
add_initial(1, 0); // South moving vs East
add_initial(2, 3); // West moving vs North
// Other diagonal and axis collisions omitted for brevity...
// (Retain your original population of pq and coord maps here)
// Setup dynamic structures for recalc
for (int d = 0; d < 4; ++d) {
coord[d].clear();
}
vector<map<int, set<array<int,2>>>> pos(4), neg(4), line(4);
for (int i = 0; i < N; ++i) {
line[a[i][2]][ (a[i][2] % 2 == 0) ? a[i][1] : a[i][0] ].insert({ (a[i][2] % 2 == 0) ? a[i][0] : 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) {
if (a[i][2] % 2 == 0)
line[a[i][2]][a[i][1]].erase({a[i][0], i});
else
line[a[i][2]][a[i][0]].erase({a[i][1], i});
pos[a[i][2]][a[i][0] + a[i][1]].erase({a[i][0], i});
neg[a[i][2]][a[i][0] - a[i][1]].erase({a[i][0], i});
};
// ins now takes current_time
auto ins = [&](int i, int current_time) {
// for each potential neighbor, compute absolute tim...
// e.g., Example for dir=0:
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 = ((*it)[0] - a[i][0]) / 2;
if (tim > 0 && tim * 2 == (*it)[0] - a[i][0]) {
int abs_t = current_time + tim;
if (abs_t > current_time) pq.push({-abs_t, i, (*it)[1]});
}
}
}
// (Similarly guard each other direction's cases with if(abs_t > current_time))
};
unordered_set<int> deleted;
while (!pq.empty()) {
int d = -pq.top()[0];
int current_time = d;
vector<int> recalc, todel;
while (!pq.empty() && -pq.top()[0] == d) {
auto [_, i, j] = pq.top();
pq.pop();
bool di = deleted.count(i), dj = deleted.count(j);
if (di && !dj) recalc.push_back(j);
else if (dj && !di) recalc.push_back(i);
else if (!di && !dj) {
todel.push_back(i);
todel.push_back(j);
}
}
sort(todel.begin(), todel.end());
todel.erase(unique(todel.begin(), todel.end()), todel.end());
for (int u : todel) {
del(u);
deleted.insert(u);
}
for (int u : recalc) {
ins(u, current_time);
}
}
for (int i = 0; i < N; ++i) {
if (!deleted.count(i))
cout << i+1 << "\n";
}
return 0;
}
