#include <bits/stdc++.h>
using namespace std;
#define piii pair<int, pair<int, int>>
const int maxN = 2e5 + 5;
vector<int> hor, ver, dg1, dg2;
set<pair<int, int>> H[maxN], V[maxN], D1[maxN], D2[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) {
/// remove D1
int pos = lower_bound(dg1.begin(), dg1.end(), p[id].x - p[id].y) - dg1.begin();
D1[pos].erase(D1[pos].find({p[id].x, id}));
auto it = D1[pos].lower_bound({p[id].x, id});
if (it != D1[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') || (t1 == 'S' && t2 == 'W'))
pq.push({num2 - num1, {id1, id2}});
}
/// remove D2
pos = lower_bound(dg2.begin(), dg2.end(), p[id].x + p[id].y) - dg2.begin();
D2[pos].erase(D2[pos].find({p[id].x, id}));
it = D2[pos].lower_bound({p[id].x, id});
if (it != D2[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') || (t1 == 'N' && t2 == 'W'))
pq.push({num2 - num1, {id1, id2}});
}
/// remove H or V
if (p[id].type == 'E' || p[id].type == 'W') {
int 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, {id1, id2}});
}
}
else {
int 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 == 'N' && t2 == 'S') pq.push({num2 - num1, {id1, id2}});
}
}
}
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
freopen("battle.inp", "r", stdin);
freopen("battle.out", "w", stdout);
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); /// -
if (p[i].type == 'S' || p[i].type == 'N') ver.push_back(p[i].x); /// |
dg1.push_back(p[i].x - p[i].y);
dg2.push_back(p[i].x + p[i].y);
}
if (hor.size() > 0) {sort(hor.begin(), hor.end()); hor.erase(unique(hor.begin(), hor.end()), hor.end());};
if (ver.size() > 0) {sort(ver.begin(), ver.end()); ver.erase(unique(ver.begin(), ver.end()), ver.end());};
sort(dg1.begin(), dg1.end()); dg1.erase(unique(dg1.begin(), dg1.end()), dg1.end());
sort(dg2.begin(), dg2.end()); dg2.erase(unique(dg2.begin(), dg2.end()), dg2.end());
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
pos = lower_bound(dg1.begin(), dg1.end(), p[i].x - p[i].y) - dg1.begin();
D1[pos].insert({p[i].x, i});
/// dg2
pos = lower_bound(dg2.begin(), dg2.end(), p[i].x + p[i].y) - dg2.begin();
D2[pos].insert({p[i].x, i});
}
/// Consider d2
for (int i = 0; i < dg2.size(); i++) {
auto it = D2[i].begin(); it++;
while (it != D2[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') || (t1 == 'N' && t2 == 'W'))
pq.push({num2 - num1, {id1, id2}});
it++;
}
}
/// Consider d1
for (int i = 0; i < dg1.size(); i++) {
auto it = D1[i].begin(); it++;
for ( ; it != D1[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') || (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, {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 == 'N' && t2 == 'S') pq.push({num2 - num1, {id1, id2}});
}
}
while (pq.size() > 0) {
auto it = pq.top(); pq.pop();
int hel = it.first, x = it.second.first, y = it.second.second;
//cout << hel << ' ' << x << ' ' << y << ' ';
if (tick[x] && tick[y]) {
//cout << "None\n";
continue;
}
if (!tick[x] && !tick[y]) {
tick[x] = tick[y] = hel;
del(x); del(y);
//cout << "All\n";
continue;
}
if (tick[x] == hel) {
tick[y] = hel;
del(y);
//cout << "Rt\n";
continue;
}
if (tick[y] == hel) {
tick[x] = hel;
del(x);
//cout << "Lt\n";
continue;
}
//cout << "None\n";
}
/*for (int i = 1; i <= n; i++)
cout << tick[i] << '\n';
cout << "RES\n";*/
vector<int> res; res.clear();
for (int i = 1; i <= n; i++)
if (!tick[i]) res.push_back(i);
if (res.size() > 0) {
for (auto v: res)
cout << v << '\n';
return 0;
}
//cout << 0;
return 0;
}
