#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define vi vector<int>
#define si set<int>
#define usi unordered_set<int>
#define sll set<ll>
#define usll unordered_set<ll>
#define vb vector<bool>
#define vll vector<ll>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vvi vector<vector<int>>
#define vvll vector<vector<ll>>
#define MAXN 2000005
int n;
pii arr[MAXN];
char c[MAXN];
bool dead[MAXN];
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>,
greater<tuple<int, int, int>>>
pq;
struct dat {
vector<int> idx;
pii cmp1, cmp2;
char ca, cb;
int nx[MAXN];
int pv[MAXN];
int dot(pii p1, pii p2) {
return p1.first * p2.first + p1.second * p2.second;
}
bool can(int i, int j) {
return dot(arr[i], cmp1) == dot(arr[j], cmp1) && c[i] == ca && c[j] == cb;
}
int dist(int i, int j) {
return abs(arr[i].first - arr[j].first) +
abs(arr[i].second - arr[j].second);
}
void init() {
memset(nx, -1, sizeof(nx));
memset(pv, -1, sizeof(pv));
if (idx.empty())
return;
sort(idx.begin(), idx.end(), [&](int &p1, int &p2) {
pii a = arr[p1], b = arr[p2];
if (dot(a, cmp1) == dot(b, cmp1))
return dot(a, cmp2) < dot(b, cmp2);
return dot(a, cmp1) < dot(b, cmp1);
});
for (int i = 0; i < (int)idx.size() - 1; i++) {
nx[idx[i]] = idx[i + 1];
pv[idx[i + 1]] = idx[i];
if (can(idx[i], idx[i + 1])) {
pq.push({dist(idx[i], idx[i + 1]), idx[i], idx[i + 1]});
}
}
}
void rem(int i) {
int nn = nx[i], pp = pv[i];
if (pp != -1)
nx[pp] = nn;
if (nn != -1)
pv[nn] = pp;
if (pp != -1 && nn != -1 && can(pp, nn))
pq.push({dist(pp, nn), pp, nn});
}
};
dat st[6];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cin >> n;
for (int i = 0; i < n; i++) {
cin >> arr[i].first >> arr[i].second >> c[i];
}
// NW, NE, SE, SW, NS, EW
st[0].cmp1 = {1, 1}, st[0].cmp2 = {1, 0}, st[0].ca = 'N', st[0].cb = 'W';
st[1].cmp1 = {-1, 1}, st[1].cmp2 = {1, 0}, st[1].ca = 'E', st[1].cb = 'N';
st[2].cmp1 = {1, 1}, st[2].cmp2 = {1, 0}, st[2].ca = 'E', st[2].cb = 'S';
st[3].cmp1 = {-1, 1}, st[3].cmp2 = {1, 0}, st[3].ca = 'S', st[3].cb = 'W';
st[4].cmp1 = {1, 0}, st[4].cmp2 = {0, 1}, st[4].ca = 'S', st[4].cb = 'N';
st[5].cmp1 = {0, 1}, st[5].cmp2 = {1, 0}, st[5].ca = 'E', st[5].cb = 'W';
/*st[0].cmp1 = {1, -1}, st[0].cmp2 = {1, 0}, st[0].ca = 'E', st[0].cb = 'N';*/
/*st[1].cmp1 = {1, 1}, st[1].cmp2 = {1, 0}, st[1].ca = 'N', st[1].cb = 'W';*/
/*st[2].cmp1 = {1, 1}, st[2].cmp2 = {1, 0}, st[2].ca = 'E', st[2].cb = 'S';*/
/*st[3].cmp1 = {1, -1}, st[3].cmp2 = {1, 0}, st[3].ca = 'S', st[3].cb = 'W';*/
/*st[4].cmp1 = {1, 0}, st[4].cmp2 = {0, 1}, st[4].ca = 'S', st[4].cb = 'N';*/
/*st[5].cmp1 = {0, 1}, st[5].cmp2 = {1, 0}, st[5].ca = 'E', st[5].cb = 'W';*/
map<char, vector<int>> M = {
{'N', {0, 1, 4}}, {'E', {1, 2, 5}}, {'S', {2, 3, 4}}, {'W', {0, 3, 5}}};
for (int i = 0; i < n; i++) {
for (int j : M[c[i]]) {
st[j].idx.push_back(i);
}
}
for (int i = 0; i < 6; i++)
st[i].init();
while (!pq.empty()) {
int w, a, b;
tie(w, a, b) = pq.top();
pq.pop();
if (dead[a] || dead[b])
continue;
si tm = {a, b};
while (!pq.empty() && get<0>(pq.top()) == w) {
tie(w, a, b) = pq.top();
pq.pop();
if (!dead[a] && !dead[b]) {
tm.insert(a);
tm.insert(b);
}
}
for (int i : tm) {
dead[i] = true;
for (auto it : M[c[i]])
st[it].rem(i);
}
}
for (int i = 0; i < n; i++)
if (!dead[i])
cout << i + 1 << "\n";
}
