#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<unordered_map<ll, map<ll, ll>>> Con;
#define sz(a) (ll)a.size()
#define all(a) a.begin(), a.end()
#define vc vector
#define pub push_back
#define pob pop_back
#define st first
#define nd second
const ll INF = 1e18;
const ll bINF = 1e10;
struct Tree {
ll base;
vc<pll> t;
Tree() = default;
Tree(ll n) {
base = 1;
while (base < n)
base *= 2;
t.assign(2 * base, {INF, 0});
for (ll i = 0; i < base; i++)
t[i + base].nd = i;
}
void set(ll i, ll x) {
i += base;
t[i].st = x;
i /= 2;
while (i >= 1) {
t[i] = min(t[2 * i], t[2 * i + 1]);
i /= 2;
}
}
pll get() {
return t[1];
}
};
struct Ship {
ll x, y, dir;
};
ll n;
vc<Ship> a;
vc<vc<ll>> c;
Con hor(2), ver(2), ascu(2), ascd(2), desu(2), desd(2);
Tree tree;
void input() {
cin >> n;
a.resize(n);
for (auto &ai : a) {
cin >> ai.x >> ai.y;
char dir;
cin >> dir;
if (dir == 'N')
ai.dir = 1;
else if (dir == 'S')
ai.dir = 0;
else if (dir == 'E')
ai.dir = 2;
else
ai.dir = 3;
}
}
void updd(Con *con, ll i, ll j, ll k, ll id) {
ll d = INF;
if (i == 0) {
auto mp = con->at(1).find(j);
if (mp != con->at(1).end()) {
auto find = mp->nd.upper_bound(k);
if (find != mp->nd.end())
d = find->st - k;
}
} else {
auto mp = con->at(0).find(j);
if (mp != con->at(0).end()) {
auto find = mp->nd.lower_bound(k);
if (find != mp->nd.begin()) {
find--;
d = k - find->st;
}
}
}
if (con == &hor)
c[0][id] = d;
else if (con == &ver)
c[1][id] = d;
else if (con == &ascu or con == &ascd)
c[2][id] = d;
else
c[3][id] = d;
tree.set(id, min(min(c[0][id] / 2, c[1][id] / 2), min(c[2][id] / 2, c[3][id] / 2)));
}
void updall(Con &con) {
for (ll i = 0; i < 2; i++)
for (auto &[j, mp] : con[i])
for (auto &[k, id] : mp)
updd(&con, i, j, k, id);
}
struct Sav {
Con *con;
ll i, j, k, id;
};
map<ll, ll> emp;
pair<Sav, Sav> rem(Con *con, ll i, ll j, ll k) {
vc<map<ll, ll> *> mp(2);
mp[i] = &con->at(i)[j];
mp[i]->erase(k);
auto fmp = con->at(i ^ 1).find(j);
if (fmp != con->at(i ^ 1).end())
mp[i ^ 1] = &(fmp->nd);
else
mp[i ^ 1] = &emp;
pair<Sav, Sav> ret = {{nullptr, -1, -1, -1, -1}, {nullptr, -1, -1, -1, -1}};
auto find = mp[0]->lower_bound(k);
if (find != mp[0]->begin()) {
find--;
ret.st = {con, 0, j, find->st, find->nd};
}
find = mp[1]->upper_bound(k);
if (find != mp[1]->end())
ret.nd = {con, 1, j, find->st, find->nd};
return ret;
}
void prepro() {
c.assign(4, vc<ll>(n, INF));
for (ll i = 0; i < n; i++) {
ll x = a[i].x;
ll y = a[i].y;
ll dir = a[i].dir;
if (dir == 0) {
ver[0][x][y] = i;
ascu[0][x - y][x + y] = i;
desu[1][x + y][x - y] = i;
} else if (dir == 1) {
ver[1][x][y] = i;
ascd[1][x - y][x + y] = i;
desd[0][x + y][x - y] = i;
} else if (dir == 2) {
hor[0][y][x] = i;
ascd[0][x - y][x + y] = i;
desu[0][x + y][x - y] = i;
} else {
hor[1][y][x] = i;
ascu[1][x - y][x + y] = i;
desd[1][x + y][x - y] = i;
}
}
tree = Tree(n);
updall(hor);
updall(ver);
updall(ascu);
updall(ascd);
updall(desu);
updall(desd);
}
void simulate() {
vc<bool> sur(n, true);
while (true) {
auto p = tree.get();
if (p.st > bINF)
break;
ll t = p.st;
vc<ll> tor;
while (true) {
p = tree.get();
if (p.st != t)
break;
tor.pub(p.nd);
tree.set(p.nd, INF);
}
vc<pair<Sav, Sav>> tou;
for (ll &id : tor) {
sur[id] = false;
ll x = a[id].x;
ll y = a[id].y;
ll dir = a[id].dir;
if (dir == 0) {
tou.pub(rem(&ver, 0, x, y));
tou.pub(rem(&ascu, 0, x - y, x + y));
tou.pub(rem(&desu, 1, x + y, x - y));
} else if (dir == 1) {
tou.pub(rem(&ver, 1, x, y));
tou.pub(rem(&ascd, 1, x - y, x + y));
tou.pub(rem(&desd, 0, x + y, x - y));
} else if (dir == 2) {
tou.pub(rem(&hor, 0, y, x));
tou.pub(rem(&ascd, 0, x - y, x + y));
tou.pub(rem(&desu, 0, x + y, x - y));
} else {
tou.pub(rem(&hor, 1, y, x));
tou.pub(rem(&ascu, 1, x - y, x + y));
tou.pub(rem(&desd, 1, x + y, x - y));
}
}
for (auto &p : tou) {
//cout << p.st.id << " " << p.nd.id << " ";
{
auto [con, i, j, k, id] = p.st;
if (id != -1 and sur[id])
updd(con, i, j, k, id);
}
auto [con, i, j, k, id] = p.nd;
if (id != -1 and sur[id])
updd(con, i, j, k, id);
}
//cout << "\n";
}
for (ll i = 0; i < n; i++)
if (sur[i])
cout << i + 1 << "\n";
}
void program() {
input();
prepro();
simulate();
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
program();
return 0;
}
