#include <bits/stdc++.h>
using namespace std;
#define ll int
#define pii pair<ll, ll>
#define fi first
#define sec second
#pragma GCC optimise ("o-fast", "unroll-loops");
const ll INF = 1e9;
const int MAXN = 2e5;
ll X[MAXN + 5], Y[MAXN + 5];
char dir[MAXN + 5];
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
ll N; cin >> N;
vector <ll> compress;
vector <ll> idx(26), dead(N + 5);
idx['U' - 'A'] = 0;
idx['D' - 'A'] = 1;
idx['L' - 'A'] = 2;
idx['R' - 'A'] = 3;
for (int i = 1; i <= N; i++) {
cin >> X[i] >> Y[i] >> dir[i];
compress.push_back(X[i]);
compress.push_back(Y[i]);
compress.push_back(X[i] + Y[i]);
compress.push_back(X[i] - Y[i]);
if (dir[i] == 'N') dir[i] = 'U';
else if (dir[i] == 'S') dir[i] = 'D';
else if (dir[i] == 'W') dir[i] = 'L';
else if (dir[i] == 'E') dir[i] = 'R';
}
vector <ll> positive(N + 5), negative(N + 5), horizontal(N + 5), vertical(N + 5);
sort(compress.begin(), compress.end());
compress.erase(unique(compress.begin(), compress.end()), compress.end());
ll M = compress.size();
vector <vector<set<pii>>> pos(4, vector<set<pii>> (M + 5));
vector <vector<set<pii>>> neg(4, vector<set<pii>> (M + 5));
vector <vector<set<pii>>> hori(4, vector<set<pii>> (M + 5));
vector <vector<set<pii>>> verti(4, vector<set<pii>> (M + 5));
auto get_id = [&](ll idx) {
return lower_bound(compress.begin(), compress.end(), idx) - compress.begin() + 1;
};
for (int i = 1; i <= N; i++) {
positive[i] = get_id(X[i] + Y[i]);
negative[i] = get_id(X[i] - Y[i]);
horizontal[i] = get_id(Y[i]);
vertical[i] = get_id(X[i]);
pos[idx[dir[i] - 'A']][positive[i]].insert({X[i], i});
neg[idx[dir[i] - 'A']][negative[i]].insert({X[i], i});
if (dir[i] == 'L' || dir[i] == 'R') hori[idx[dir[i] - 'A']][horizontal[i]].insert({X[i], i});
if (dir[i] == 'U' || dir[i] == 'D') verti[idx[dir[i] - 'A']][vertical[i]].insert({Y[i], i});
}
priority_queue <pair<ll, pii>> pq;
auto id = [&](char c) {
return idx[c - 'A'];
};
auto add = [&](ll idx) {
if (dir[idx] == 'U') {
// cek D
auto x = verti[id('D')][vertical[idx]].lower_bound({Y[idx], -1});
if (x != verti[id('D')][vertical[idx]].begin()) {
--x;
pq.push({-(abs(Y[idx] - (*x).fi) / 2), {idx, (*x).sec}});
}
// cek positive
x = pos[id('L')][positive[idx]].upper_bound({X[idx], -1});
if (x != pos[id('L')][positive[idx]].end()) {
pq.push({-abs(X[idx] - (*x).fi), {idx, (*x).sec}});
}
// cek negative
x = neg[id('R')][negative[idx]].lower_bound({X[idx], -1});
if (x != neg[id('R')][negative[idx]].begin()) {
--x;
pq.push({-abs(X[idx] - (*x).fi), {idx, (*x).sec}});
}
}
else if (dir[idx] == 'D') {
// cek U
auto x = verti[id('U')][vertical[idx]].lower_bound({Y[idx], -1});
if (x != verti[id('U')][vertical[idx]].end()) {
pq.push({-(abs(Y[idx] - (*x).fi) / 2), {idx, (*x).sec}});
}
// cek positive
x = pos[id('R')][positive[idx]].lower_bound({X[idx], -1});
if (x != pos[id('R')][positive[idx]].begin()) {
--x;
pq.push({-abs(X[idx] - (*x).fi), {idx, (*x).sec}});
}
// cek negative
x = neg[id('L')][negative[idx]].upper_bound({X[idx], -1});
if (x != neg[id('L')][negative[idx]].end()) {
pq.push({-abs(X[idx] - (*x).fi), {idx, (*x).sec}});
}
}
else if (dir[idx] == 'R') {
// cek L
auto x = hori[id('L')][horizontal[idx]].upper_bound({X[idx], -1});
if (x != hori[id('L')][horizontal[idx]].end()) {
pq.push({-(abs(X[idx] - (*x).fi) / 2), {idx, (*x).sec}});
}
// cek positive
x = pos[id('D')][positive[idx]].upper_bound({X[idx], -1});
if (x != pos[id('D')][positive[idx]].end()) {
pq.push({-abs(X[idx] - (*x).fi), {idx, (*x).sec}});
}
// cek negative
x = neg[id('U')][negative[idx]].upper_bound({X[idx], -1});
if (x != neg[id('U')][negative[idx]].end()) {
pq.push({-abs(X[idx] - (*x).fi), {idx, (*x).sec}});
}
}
else {
// cek R
auto x = hori[id('R')][horizontal[idx]].lower_bound({X[idx], -1});
if (x != hori[id('R')][horizontal[idx]].begin()) {
--x;
pq.push({-(abs(X[idx] - (*x).fi) / 2), {idx, (*x).sec}});
}
// cek positive
x = pos[id('U')][positive[idx]].upper_bound({X[idx], -1});
if (x != pos[id('U')][positive[idx]].begin()) {
--x;
pq.push({-abs(X[idx] - (*x).fi), {idx, (*x).sec}});
}
// cek negative
x = neg[id('D')][negative[idx]].upper_bound({X[idx], -1});
if (x != neg[id('D')][negative[idx]].begin()) {
--x;
pq.push({-abs(X[idx] - (*x).fi), {idx, (*x).sec}});
}
}
};
auto del = [&](ll i) {
pos[idx[dir[i] - 'A']][positive[i]].erase({X[i], i});
neg[idx[dir[i] - 'A']][negative[i]].erase({X[i], i});
if (dir[i] == 'L' || dir[i] == 'R') hori[idx[dir[i] - 'A']][horizontal[i]].erase({X[i], i});
if (dir[i] == 'U' || dir[i] == 'D') verti[idx[dir[i] - 'A']][vertical[i]].erase({Y[i], i});
};
for (int i = 1; i <= N; i++) {
add(i);
}
while (!pq.empty()) {
ll lst = -1;
vector <pii> op;
while (!pq.empty() && (lst == -1 || pq.top().fi == -lst)) {
op.push_back({pq.top().sec.fi, pq.top().sec.sec});
lst = -pq.top().fi;
pq.pop();
}
// cout << lst << "\n";
vector <ll> v;
for (auto [i, j] : op) {
if (dead[i] || dead[j]) {
if (!dead[i]) add(i);
if (!dead[j]) add(j);
}
else {
del(i), del(j);
v.push_back(i);
v.push_back(j);
}
}
for (auto i : v) dead[i] = 1;
}
for (int i = 1; i <= N; i++) {
if (!dead[i]) cout << i << "\n";
}
}
/*
*/
