#include <bits/stdc++.h>
using namespace std;
#define piii pair<int, pair<int, int>>
const int maxN = 2e5 + 5;
vector<int> hor, ver, dg1_en, dg1_sw, dg2_es, dg2_nw;
set<pair<int, int>> H[maxN], V[maxN], D1_EN[maxN], D1_SW[maxN], D2_ES[maxN], D2_NW[maxN];
struct point {
int x, y; char type;
} p[maxN];
int tick[maxN];
priority_queue<piii, vector<piii>, greater<piii>> pq;
void del(int id) {
int pos;
/// remove D1_EN
if (p[id].type == 'E' || p[id].type == 'N') {
pos = lower_bound(dg1_en.begin(), dg1_en.end(), p[id].x - p[id].y) - dg1_en.begin();
D1_EN[pos].erase(D1_EN[pos].find({p[id].x, id}));
auto it = D1_EN[pos].lower_bound({p[id].x, id});
if (it != D1_EN[pos].end()) {
auto it2 = it; it2--;
auto [num1, id1] = *it2; auto [num2, id2] = *it;
char t1 = p[id1].type, t2 = p[id2].type;
if (t1 == 'E' && t2 == 'N') pq.push({num2 - num1, {id1, id2}});
}
}
else {
/// remove D1_SW
pos = lower_bound(dg1_sw.begin(), dg1_sw.end(), p[id].x - p[id].y) - dg1_sw.begin();
D1_SW[pos].erase(D1_SW[pos].find({p[id].x, id}));
auto it = D1_SW[pos].lower_bound({p[id].x, id});
if (it != D1_SW[pos].end()) {
auto it2 = it; it2--;
auto [num1, id1] = *it2; auto [num2, id2] = *it;
char t1 = p[id1].type, t2 = p[id2].type;
if (t1 == 'S' && t2 == 'W') pq.push({num2 - num1, {id1, id2}});
}
}
/// remove D2_ES
if (p[id].type == 'E' || p[id].type == 'S') {
pos = lower_bound(dg2_es.begin(), dg2_es.end(), p[id].x + p[id].y) - dg2_es.begin();
D2_ES[pos].erase(D2_ES[pos].find({p[id].x, id}));
auto it = D2_ES[pos].lower_bound({p[id].x, id});
if (it != D2_ES[pos].end()) {
auto it2 = it; it2--;
auto [num1, id1] = *it2; auto[num2, id2] = *it;
char t1 = p[id1].type, t2 = p[id2].type;
if (t1 == 'E' && t2 == 'S') pq.push({num2 - num1, {id1, id2}});
}
}
else {
pos = lower_bound(dg2_nw.begin(), dg2_nw.end(), p[id].x + p[id].y) - dg2_nw.begin();
D2_NW[pos].erase(D2_NW[pos].find({p[id].x, id}));
auto it = D2_NW[pos].lower_bound({p[id].x, id});
if (it != D2_NW[pos].end()) {
auto it2 = it; it2--;
auto [num1, id1] = *it2; auto[num2, id2] = *it;
char t1 = p[id1].type, t2 = p[id2].type;
if (t1 == 'N' && t2 == 'W') pq.push({num2 - num1, {id1, id2}});
}
}
/// remove H or V
if (p[id].type == 'E' || p[id].type == 'W') {
pos = lower_bound(hor.begin(), hor.end(), p[id].y) - hor.begin();
H[pos].erase(H[pos].find({p[id].x, id}));
auto it = H[pos].lower_bound({p[id].x, id});
if (it != H[pos].end()) {
auto it2 = it; it2--;
auto [num1, id1] = *it2; auto [num2, id2] = *it;
char t1 = p[id1].type, t2 = p[id2].type;
if (t1 == 'E' && t2 == 'W') pq.push({(num2 - num1) / 2, {id1, id2}});
}
}
else {
pos = lower_bound(ver.begin(), ver.end(), p[id].x) - ver.begin();
V[pos].erase(V[pos].find({p[id].y, id}));
auto it = V[pos].lower_bound({p[id].y, id});
if (it != V[pos].end()) {
auto it2 = it; it2--;
auto [num1, id1] = *it2; auto [num2, id2] = *it;
char t1 = p[id1].type, t2 = p[id2].type;
if (t1 == 'S' && t2 == 'N') pq.push({(num2 - num1) / 2, {id1, id2}});
}
}
}
void compress(vector<int> &a) {
if (a.size() > 0) {
sort(a.begin(), a.end());
a.erase(unique(a.begin(), a.end()), a.end());
}
}
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> p[i].x >> p[i].y >> p[i].type;
if (p[i].type == 'E' || p[i].type == 'W') hor.push_back(p[i].y); /// -
else ver.push_back(p[i].x); /// |
if (p[i].type == 'E' || p[i].type == 'N') dg1_en.push_back(p[i].x - p[i].y);
else dg1_sw.push_back(p[i].x - p[i].y);
if (p[i].type == 'E' || p[i].type == 'S') dg2_es.push_back(p[i].x + p[i].y);
else dg2_nw.push_back(p[i].x + p[i].y);
}
compress(hor); compress(ver);
compress(dg1_en); compress(dg1_sw);
compress(dg2_es); compress(dg2_nw);
for (int i = 1; i <= n; i++) {
int pos;
/// hor
if (p[i].type == 'E' || p[i].type == 'W') {
pos = lower_bound(hor.begin(), hor.end(), p[i].y) - hor.begin();
H[pos].insert({p[i].x, i});
}
else {
/// ver
pos = lower_bound(ver.begin(), ver.end(), p[i].x) - ver.begin();
V[pos].insert({p[i].y, i});
}
/// dg1
if (p[i].type == 'E' || p[i].type == 'N') {
pos = lower_bound(dg1_en.begin(), dg1_en.end(), p[i].x - p[i].y) - dg1_en.begin();
D1_EN[pos].insert({p[i].x, i});
}
else {
pos = lower_bound(dg1_sw.begin(), dg1_sw.end(), p[i].x - p[i].y) - dg1_sw.begin();
D1_SW[pos].insert({p[i].x, i});
}
/// dg2
if (p[i].type == 'E' || p[i].type == 'S') {
pos = lower_bound(dg2_es.begin(), dg2_es.end(), p[i].x + p[i].y) - dg2_es.begin();
D2_ES[pos].insert({p[i].x, i});
}
else {
pos = lower_bound(dg2_nw.begin(), dg2_nw.end(), p[i].x + p[i].y) - dg2_nw.begin();
D2_NW[pos].insert({p[i].x, i});
}
}
/// Consider d2
for (int i = 0; i < dg2_es.size(); i++) {
auto it = D2_ES[i].begin(); it++;
while (it != D2_ES[i].end()) {
auto it2 = it; it2--;
auto [num1, id1] = *it2; auto [num2, id2] = *it;
char t1 = p[id1].type, t2 = p[id2].type;
if (t1 == 'E' && t2 == 'S') pq.push({num2 - num1, {id1, id2}});
it++;
}
}
for (int i = 0; i < dg2_nw.size(); i++) {
auto it = D2_NW[i].begin(); it++;
while (it != D2_NW[i].end()) {
auto it2 = it; it2--;
auto [num1, id1] = *it2; auto [num2, id2] = *it;
char t1 = p[id1].type, t2 = p[id2].type;
if (t1 == 'N' && t2 == 'W') pq.push({num2 - num1, {id1, id2}});
it++;
}
}
/// Consider d1
for (int i = 0; i < dg1_en.size(); i++) {
auto it = D1_EN[i].begin(); it++;
for ( ; it != D1_EN[i].end(); it++) {
auto it2 = it; it2--;
auto [num1, id1] = *it2; auto [num2, id2] = *it;
char t1 = p[id1].type, t2 = p[id2].type;
if (t1 == 'E' && t2 == 'N') pq.push({num2 - num1, {id1, id2}});
}
}
for (int i = 0; i < dg1_sw.size(); i++) {
auto it = D1_SW[i].begin(); it++;
for ( ; it != D1_SW[i].end(); it++) {
auto it2 = it; it2--;
auto [num1, id1] = *it2; auto [num2, id2] = *it;
char t1 = p[id1].type, t2 = p[id2].type;
if (t1 == 'S' && t2 == 'W') pq.push({num2 - num1, {id1, id2}});
}
}
/// Consider hor
for (int i = 0; i < hor.size(); i++) {
auto it = H[i].begin(); it++;
for ( ; it != H[i].end(); it++) {
auto it2 = it; it2--;
auto [num1, id1] = *it2; auto [num2, id2] = *it;
char t1 = p[id1].type, t2 = p[id2].type;
if (t1 == 'E' && t2 == 'W') pq.push({(num2 - num1) / 2, {id1, id2}});
}
}
/// Consider ver
for (int i = 0; i < ver.size(); i++) {
auto it = V[i].begin(); it++;
for ( ; it != V[i].end(); it++) {
auto it2 = it; it2--;
auto [num1, id1] = *it2; auto [num2, id2] = *it;
char t1 = p[id1].type, t2 = p[id2].type;
if (t1 == 'S' && t2 == 'N') pq.push({(num2 - num1) / 2, {id1, id2}});
}
}
while (pq.size() > 0) {
auto it = pq.top(); pq.pop();
int hel = it.first, x = it.second.first, y = it.second.second;
if (tick[x] && tick[y]) continue;
if (!tick[x] && !tick[y]) {
tick[x] = tick[y] = hel;
del(x); del(y);
continue;
}
if (tick[x] == hel) {
tick[y] = hel;
del(y);
continue;
}
if (tick[y] == hel) {
tick[x] = hel;
del(x);
continue;
}
}
vector<int> res; res.clear();
for (int i = 1; i <= n; i++)
if (!tick[i]) res.push_back(i);
for (auto v: res)
cout << v << '\n';
return 0;
}
