#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Ship {
int id;
int 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<int>> rows;
map<ll, set<int>> cols;
map<ll, set<int>> diag1;
map<ll, set<int>> diag2;
priority_queue<Event, vector<Event>, greater<Event>> pq;
vector<char> dead;
vector<Ship> ships;
void checkRows(int i, int j) {
if (i == -1 || j == -1)
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 == -1 || j == -1)
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 == -1 || j == -1)
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 == -1 || j == -1)
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].id);
cols[ships[i].x].insert(ships[i].id);
diag1[ships[i].x + ships[i].y].insert(ships[i].id);
diag2[ships[i].x - ships[i].y].insert(ships[i].id);
}
auto init = [&](map<ll, set<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, *next(it));
}
}
};
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);
}
for (int id : dying) {
dead[id] = 1;
auto handle = [&](map<ll, set<int>> &m, ll val, void (*func)(int, int)) {
auto &s = m[val];
auto it = s.find(id);
int prev_it = (it == s.begin() ? -1 : *prev(it));
int next_it = (it == s.end() ? -1 : *next(it));
s.erase(it);
func(prev_it, next_it);
};
handle(rows, ships[id - 1].y, checkRows);
handle(cols, ships[id - 1].x, checkCols);
handle(diag1, ships[id - 1].x + ships[id - 1].y, checkDiag1);
handle(diag2, ships[id - 1].x - ships[id - 1].y, checkDiag2);
}
}
for (int i = 1; i < n + 1; ++i) {
if (!dead[i])
cout << i << "\n";
}
return 0;
}
