#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);
vector<pii> shipCoord(N);
vector<char> shipDir(N);
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;
shipCoord[i] = {x, y};
shipDir[i] = c;
S[indMap[c]].push_back({x, y, i});
}
vb active(N, true);
vector<map<int, map<int, Ship>>> mp1(4), mp2(4), mp3(4), mp4(4);
for (int i = 0; i < 4; i++) {
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[i][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[i][ix][key] = j;
}
}
for (int i : {2, 3}) {
for (auto j : S[i]) {
int ix = (i == 2 ? j.x : j.y);
int rix = (i == 2 ? j.y : j.x);
mp3[i][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);
mp4[i][ix][rix] = j;
}
}
bool cont = true;
while (cont) {
cont = false;
// actual logic is here
for (int i = 0; i < 4; i++) {
// take care of the diagonals
for (auto k = mp1[i].begin(); k != mp1[i].end();) {
if (i <= 1) {
while (k->second.size() > 0 && !active[k->second.begin()->second.ix])
k->second.erase(k->second.begin());
if (k->second.empty()) {
k = mp1[i].erase(k);
continue;
}
auto j = k->second.begin();
map<int, Ship>::iterator match;
if (mp2[i][k->first].size() == 0) {
k++;
continue;
}
if (i == 0)
match = mp2[i][k->first].lower_bound(j->second.y);
else
match = mp2[i][k->first].lower_bound(j->second.x);
if (match == mp2[i][k->first].begin()) {
k++;
continue;
}
--match;
int xdiff = abs(j->second.x - match->second.x);
pq.push(make_tuple(xdiff, j->second.ix, match->second.ix));
mp2[i][k->first].erase(match);
} else {
while (k->second.size() > 0 && !active[k->second.rbegin()->second.ix])
k->second.erase(--k->second.end());
if (k->second.empty()) {
k = mp1[i].erase(k);
continue;
}
auto j = k->second.rbegin();
map<int, Ship>::iterator match;
if (mp2[i][k->first].size() == 0) {
k++;
continue;
}
if (i == 2)
match = mp2[i][k->first].lower_bound(j->second.y);
else
match = mp2[i][k->first].lower_bound(j->second.x);
if (match == mp2[i][k->first].end()) {
k++;
continue;
}
int xdiff = abs(j->second.x - match->second.x);
pq.push(make_tuple(xdiff, j->second.ix, match->second.ix));
mp2[i][k->first].erase(match);
}
k++;
}
}
for (int i : {2, 3}) {
for (auto k = mp3[i].begin(); k != mp3[i].end();) {
while (k->second.size() > 0 && !active[k->second.rbegin()->second.ix])
k->second.erase(--k->second.end());
if (k->second.empty()) {
k = mp3[i].erase(k);
continue;
}
auto j = k->second.rbegin();
map<int, Ship>::iterator match;
if (i == 2) {
match = mp4[i][k->first].lower_bound(j->second.y);
} else {
match = mp4[i][k->first].lower_bound(j->second.x);
}
if (match == mp4[i][k->first].end()) {
k++;
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));
mp4[i][k->first].erase(match);
k++;
}
}
ll tprev = -1;
vll buffer;
vll repush;
while (!pq.empty()) {
cont = true;
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);
} else {
repush.push_back(x);
repush.push_back(y);
}
tprev = t;
}
for (auto j : buffer)
active[j] = false;
for (int i : repush) {
if (active[i]) {
int curDir = indMap[shipDir[i]];
Ship j = {shipCoord[i].first, shipCoord[i].second, curDir};
int ni = (curDir + 4 - 1) % 4;
int n2i = (curDir - 2 + 4) % 4;
int ix = j.x + (ni % 2 == 0 ? 1 : -1) * j.y;
int key = (ni % 2 == 0) ? j.y : j.x;
mp2[ni][ix][key] = j;
if (curDir == 0 || curDir == 1) {
int ix = (n2i == 2 ? j.x : j.y);
int rix = (n2i == 2 ? j.y : j.x);
mp4[n2i][ix][rix] = j;
}
}
}
}
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();
}
