#include <bits/stdc++.h>
#include <queue>
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>>
void printTuple(tuple<ll, ll, char> &t) {
cout << get<0>(t) << " " << get<1>(t) << " " << get<2>(t) << endl;
}
struct Ship {
int x, y, ix;
};
void solve() {
// need 3 different ways of sorting
// 0. along x + y
// 1. along x - y
// 2. along the direction of travel (y for N/S, x for E/W)
ll N;
cin >> N;
vector<vector<Ship>> S(4);
map<char, int> indMap;
indMap['N'] = 0;
indMap['W'] = 1;
indMap['S'] = 2;
indMap['E'] = 3;
priority_queue<tuple<ll, ll, ll>, vector<tuple<ll, ll, ll>>,
greater<tuple<ll, ll, ll>>>
pq;
int x, y;
char c;
for (int i = 0; i < N; i++) {
cin >> x >> y >> c;
S[indMap[c]].push_back({x, y, i});
}
for (int i = 0; i < 4; i++) {
map<int, map<int, Ship>> mp1, mp2;
for (auto j : S[i]) {
int ix = j.x + (i % 2 == 0 ? 1 : -1) * j.y;
int key = (i % 2 == 0) ? j.y : j.x;
mp1[ix][key] = j;
}
for (auto j : S[(i + 1) % 4]) {
int ix = j.x + (i % 2 == 0 ? 1 : -1) * j.y;
int key = (i % 2 == 0) ? j.y : j.x;
mp2[ix][key] = j;
}
// take care of the diagonals
for (auto &k : mp1) {
if (i <= 1) {
for (auto j = k.second.begin(); j != k.second.end(); j++) {
map<int, Ship>::iterator match;
if (mp2[k.first].size() == 0)
continue;
if (i == 0)
match = mp2[k.first].lower_bound(j->second.y);
else
match = mp2[k.first].lower_bound(j->second.x);
if (match == mp2[k.first].begin())
continue;
--match;
int xdiff = abs(j->second.x - match->second.x);
pq.push(make_tuple(xdiff, j->second.ix, match->second.ix));
mp2[k.first].erase(match);
}
} else {
for (auto j = k.second.rbegin(); j != k.second.rend(); j++) {
map<int, Ship>::iterator match;
if (mp2[k.first].size() == 0)
continue;
if (i == 2)
match = mp2[k.first].lower_bound(j->second.y);
else
match = mp2[k.first].lower_bound(j->second.x);
if (match == mp2[k.first].end())
continue;
int xdiff = abs(j->second.x - match->second.x);
pq.push(make_tuple(xdiff, j->second.ix, match->second.ix));
mp2[k.first].erase(match);
}
}
}
}
for (int i : {2, 3}) {
map<int, map<int, Ship>> mp1, mp2;
for (auto j : S[i]) {
int ix = (i == 2 ? j.x : j.y);
int rix = (i == 2 ? j.y : j.x);
mp1[ix][rix] = j;
}
for (auto j : S[(i + 2) % 4]) {
int ix = (i == 2 ? j.x : j.y);
int rix = (i == 2 ? j.y : j.x);
mp2[ix][rix] = j;
}
for (auto &k : mp1) {
for (auto j = k.second.begin(); j != k.second.end(); j++) {
map<int, Ship>::iterator match;
if (i == 2)
match = mp2[k.first].lower_bound(j->second.y);
else
match = mp2[k.first].lower_bound(j->second.x);
if (match == mp2[k.first].end())
continue;
int diff = (i == 2) ? abs(j->second.y - match->second.y) / 2
: abs(j->second.x - match->second.x) / 2;
pq.push(make_tuple(diff, j->second.ix, match->second.ix));
mp2[k.first].erase(match);
}
}
}
vb active(N, true);
ll tprev = -1;
vll buffer;
while (!pq.empty()) {
auto [t, x, y] = pq.top();
if (t > tprev) {
for (auto j : buffer)
active[j] = false;
buffer.clear();
}
pq.pop();
if (active[x] && active[y]) {
buffer.push_back(x);
buffer.push_back(y);
}
tprev = t;
}
for (auto j : buffer)
active[j] = false;
for (int i = 0; i < N; i++) {
if (active[i])
cout << i + 1 << "\n";
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
solve();
}
