#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 { return t > o.t; }
};
int n;
map<ll, set<pair<ll, int>>> rows, cols, diag1, diag2;
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 - 1].dir == 'E' && ships[j - 1].dir == 'W') {
pq.push({(ships[j - 1].x - ships[i - 1].x) / 2, i, j});
}
}
void checkCols(int i, int j) {
if (i <= 0 || j <= 0)
return;
if (ships[i - 1].dir == 'S' && ships[j - 1].dir == 'N') {
pq.push({(ships[j - 1].y - ships[i - 1].y) / 2, i, j});
}
}
void checkDiag1(int i, int j) {
if (i <= 0 || j <= 0)
return;
if ((ships[i - 1].dir == 'E' && ships[j - 1].dir == 'S') ||
(ships[i - 1].dir == 'N' && ships[j - 1].dir == 'W')) {
pq.push({(ships[j - 1].x - ships[i - 1].x), i, j});
}
}
void checkDiag2(int i, int j) {
if (i <= 0 || j <= 0)
return;
if ((ships[i - 1].dir == 'E' && ships[j - 1].dir == 'N') ||
(ships[i - 1].dir == 'S' && ships[j - 1].dir == 'W')) {
pq.push({(ships[j - 1].x - ships[i - 1].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 = 0; i < n; ++i) {
cin >> ships[i].x >> ships[i].y >> ships[i].dir;
ships[i].id = i + 1;
rows[ships[i].y].insert({ships[i].x, ships[i].id});
cols[ships[i].x].insert({ships[i].y, ships[i].id});
diag1[ships[i].x + ships[i].y].insert({ships[i].x, ships[i].id});
diag2[ships[i].x - ships[i].y].insert({ships[i].x, ships[i].id});
}
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);
init(diag1, checkDiag1);
init(diag2, checkDiag2);
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) {
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])
func(prev_it, next_it);
};
handle(rows, ships[id - 1].y, checkRows, ships[id - 1].x);
handle(cols, ships[id - 1].x, checkCols, ships[id - 1].y);
handle(diag1, ships[id - 1].x + ships[id - 1].y, checkDiag1,
ships[id - 1].x);
handle(diag2, ships[id - 1].x - ships[id - 1].y, checkDiag2,
ships[id - 1].x);
}
}
for (int i = 1; i < n + 1; ++i) {
if (!dead[i])
cout << i << "\n";
}
return 0;
}
