#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Ship {
int id;
ll x, y;
char dir;
};
struct Event {
ll t;
int x, y;
bool operator>(const Event &o) const {
if (t != o.t)
return t > o.t;
if (x != o.x)
return x > o.x;
return y > o.y;
}
};
int n;
map<ll, set<pair<ll, int>>> diag[4], rows, cols;
priority_queue<Event, vector<Event>, greater<Event>> pq;
vector<char> dead;
vector<Ship> ships;
void checkRows(int i, int j) {
if (i <= 0 || j <= 0)
return;
if (ships[i].dir == 'E' && ships[j].dir == 'W') {
pq.push({(ships[j].x - ships[i].x) / 2, i, j});
}
}
void checkCols(int i, int j) {
if (i <= 0 || j <= 0)
return;
if (ships[i].dir == 'S' && ships[j].dir == 'N') {
pq.push({(ships[j].y - ships[i].y) / 2, i, j});
}
}
void checkD(int i, int j, int type) {
if (i <= 0 || j <= 0)
return;
pq.push({abs(ships[j].x - ships[i].x), i, j});
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
ships.resize(n + 1);
dead.assign(n + 1, 0);
for (int i = 1; i < n + 1; ++i) {
cin >> ships[i].x >> ships[i].y >> ships[i].dir;
ships[i].id = i;
if (ships[i].dir == 'E' || ships[i].dir == 'W')
rows[ships[i].y].insert({ships[i].x, i});
else
cols[ships[i].x].insert({ships[i].y, i});
if (ships[i].dir == 'E' || ships[i].dir == 'S')
diag[0][ships[i].x + ships[i].y].insert({ships[i].x, i});
if (ships[i].dir == 'S' || ships[i].dir == 'W')
diag[1][ships[i].x - ships[i].y].insert({ships[i].x, i});
if (ships[i].dir == 'N' || ships[i].dir == 'W')
diag[2][ships[i].x + ships[i].y].insert({ships[i].x, i});
if (ships[i].dir == 'E' || ships[i].dir == 'N')
diag[3][ships[i].x - ships[i].y].insert({ships[i].x, i});
}
auto init = [&](map<ll, set<pair<ll, int>>> &m, void (*func)(int, int)) {
for (auto &line : m) {
auto &s = line.second;
if (s.size() < 2)
continue;
for (auto it = s.begin(); next(it) != s.end(); ++it) {
func(it->second, next(it)->second);
}
}
};
init(rows, checkRows);
init(cols, checkCols);
for (int i = 0; i < 4; i++) {
for (auto &line : diag[i]) {
auto &s = line.second;
for (auto it = s.begin(); next(it) != s.end(); ++it) {
int u = it->second, v = next(it)->second;
if (i == 0 && ships[u].dir == 'E' && ships[v].dir == 'S')
checkD(u, v, 0);
if (i == 1 && ships[u].dir == 'S' && ships[v].dir == 'W')
checkD(u, v, 1);
if (i == 2 && ships[u].dir == 'N' && ships[v].dir == 'W')
checkD(u, v, 2);
if (i == 3 && ships[u].dir == 'E' && ships[v].dir == 'N')
checkD(u, v, 3);
}
}
}
while (!pq.empty()) {
ll curT = pq.top().t;
vector<pair<int, int>> curr;
while (!pq.empty() && pq.top().t == curT) {
Event e = pq.top();
pq.pop();
if (!dead[e.x] && !dead[e.y])
curr.push_back({e.x, e.y});
}
set<int> dying;
for (auto &[x, y] : curr) {
dying.insert(x);
dying.insert(y);
}
if (dying.empty())
continue;
for (int id : dying) {
dead[id] = 1;
}
for (int id : dying) {
auto handle = [&](map<ll, set<pair<ll, int>>> &m, ll val,
void (*func)(int, int), ll cord, int type) {
auto &s = m[val];
auto it = s.find({cord, id});
if (it == s.end())
return;
int prev_it = (it == s.begin() ? -1 : prev(it)->second);
int next_it = (next(it) == s.end() ? -1 : next(it)->second);
s.erase(it);
if (prev_it != -1 && next_it != -1 && !dead[prev_it] &&
!dead[next_it]) {
if (type == -1)
checkRows(prev_it, next_it);
else if (type == -2)
checkCols(prev_it, next_it);
else {
if (type == 0 && ships[prev_it].dir == 'E' &&
ships[next_it].dir == 'S')
checkD(prev_it, next_it, 0);
if (type == 1 && ships[prev_it].dir == 'S' &&
ships[next_it].dir == 'W')
checkD(prev_it, next_it, 1);
if (type == 2 && ships[prev_it].dir == 'N' &&
ships[next_it].dir == 'W')
checkD(prev_it, next_it, 2);
if (type == 3 && ships[prev_it].dir == 'E' &&
ships[next_it].dir == 'N')
checkD(prev_it, next_it, 3);
}
}
};
if (ships[id].dir == 'E' || ships[id].dir == 'W')
handle(rows, ships[id].y, nullptr, ships[id].x, -1);
else
handle(cols, ships[id].x, nullptr, ships[id].y, -2);
handle(diag[0], ships[id].x + ships[id].y, nullptr, ships[id].x, 0);
handle(diag[1], ships[id].x - ships[id].y, nullptr, ships[id].x, 1);
handle(diag[2], ships[id].x + ships[id].y, nullptr, ships[id].x, 2);
handle(diag[3], ships[id].x - ships[id].y, nullptr, ships[id].x, 3);
}
}
for (int i = 1; i < n + 1; ++i) {
if (!dead[i])
cout << i << "\n";
}
return 0;
}
