#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
struct SHIP {
int x, y;
char dir;
int ind;
};
struct ARROW {
int cord;
int open;
int linenumber;
SHIP ship;
};
bool operator<(const ARROW& a, const ARROW& b) {
return a.cord < b.cord;
}
VI removed;
set<pair<int, PII>> orz;
struct LINE {
set<ARROW> a;
ARROW (*func)(SHIP);
LINE(){}
LINE(ARROW (*f)(SHIP)) {
func = f;
}
bool add(SHIP s) {
ARROW ret = func(s);
if (ret.open == -1) return false;
a.insert(ret);
return true;
}
void init() {
for (auto cur = a.begin(); cur != a.end(); cur++) {
auto nxt = next(cur);
if (nxt == a.end()) break;
if (cur->open && !nxt->open) orz.insert({(nxt->cord - cur->cord)/2, {cur->ship.ind, nxt->ship.ind}});
}
}
void rem(SHIP s) {
int cord = func(s).cord;
auto it = a.lower_bound(ARROW{cord});
if (it != a.begin() && next(it) != a.end()) {
if (prev(it)->open == true && next(it)->open == false) {
orz.insert({(next(it)->cord - prev(it)->cord)/2,
{next(it)->ship.ind, prev(it)->ship.ind}});
}
}
a.erase(it);
}
};
void solve() {
int n;
cin >> n;
vector<SHIP> a(n);
vector<SHIP> original(n+1);
rep(i, n) {
int x, y;
char d;
cin >> x >> y >> d;
a[i] = {x, y, d, i+1};
original[i+1] = {x, y, d, i+1};
}
vector<vector<vector<LINE>::iterator>> whereis(n+1);
vector<LINE> lines;
lines.reserve(1e6);
auto add = [&](ARROW(*f)(SHIP)) {
bool flag = true;
rep(i, n) {
/*cout << "PROCESSING " << a[i].ind << " WITH LINENUMBER " << f(a[i]).linenumber << endl;*/
if (f(a[i]).open == -1) continue;
if (flag || lines.back().a.begin()->linenumber != f(a[i]).linenumber) {
/*cout << "ADDED NEW LINE FOR IT " << endl;*/
lines.pb(LINE(f));
flag = false;
}
if (lines.back().add(a[i])) whereis[a[i].ind].pb(lines.end()-1);
}
};
sort(all(a), [](SHIP a, SHIP b){return a.x < b.x;});
add([](SHIP a){
if (a.dir != 'N' && a.dir != 'S') return ARROW{-1, -1};
return ARROW{a.y, a.dir == 'S', a.x, a};});
sort(all(a), [](SHIP a, SHIP b){return a.y < b.y;});
add([](SHIP a){
if (a.dir != 'E' && a.dir != 'W') return ARROW{-1, -1};
return ARROW{a.x, a.dir == 'E', a.y, a};});
sort(all(a), [](SHIP a, SHIP b){return a.x+a.y < b.x+b.y;});
add([](SHIP a){
if (a.dir != 'E' && a.dir != 'S') return ARROW{-1, -1};
return ARROW{a.x-a.y, a.dir == 'E', a.x+a.y, a};});
add([](SHIP a){
if (a.dir != 'N' && a.dir != 'W') return ARROW{-1, -1};
return ARROW{a.x-a.y, a.dir == 'N', a.x+a.y, a};});
sort(all(a), [](SHIP a, SHIP b){return a.x-a.y < b.x-b.y;});
add([](SHIP a){
if (a.dir != 'E' && a.dir != 'N') return ARROW{-1, -1};
return ARROW{a.x+a.y, a.dir == 'E', a.x-a.y, a};});
add([](SHIP a){
if (a.dir != 'S' && a.dir != 'W') return ARROW{-1, -1};
return ARROW{a.x+a.y, a.dir == 'S', a.x-a.y, a};});
for (auto& ln : lines) ln.init();
/*for (auto[time, p] : orz) {*/
/* cout << "AT TIME " << time << ", NODES (" << p.ff << ", " << p.ss << ")" << endl;*/
/*}*/
/*int ind = 0;*/
/*for (auto ln : lines) {*/
/* ind++;*/
/* if (ln.a.size() == 0) continue;*/
/* cout << "LINE " << ind-1 << endl;*/
/* for (auto p : ln.a) cout << p.ship.ind << " ";*/
/* cout << endl;*/
/* for (auto p : ln.a) cout << p.cord << " ";*/
/* cout << endl;*/
/* for (auto p : ln.a) cout << p.open << " ";*/
/* cout << endl;*/
/*}*/
/*return;*/
removed = VI(n+1);
while (true) {
vector<pair<int, PII>> buf;
auto it = orz.begin();
for (; it != orz.end(); it++) {
if (it != orz.begin() && it->ff != prev(it)->ff) break;
if (!removed[it->ss.ff] && !removed[it->ss.ss]) buf.pb({it->ff, it->ss});
}
while (it != orz.begin()) orz.erase(prev(it));
/*cout << "AT THIS ROUND REMOVED FOLLOWING NODES" << endl;*/
set<int> toremove;
for (auto[W, P] : buf) {
toremove.insert(P.ff);
toremove.insert(P.ss);
}
for (auto i : toremove) {
/*if (!removed[i]) for (auto it : whereis[i]) (*it).rem(original[i]);*/
/*removed[i] = true;*/
/*if (!removed[j]) for (auto it : whereis[j]) (*it).rem(original[j]);*/
/*removed[j] = true;*/
removed[i] = true;
for (auto it : whereis[i]) (*it).rem(original[i]);
}
if (orz.size() == 0) break;
}
replr(i, 1, n) if (!removed[i]) cout << i << endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
/*freopen("mincross.in", "r", stdin); */
/*freopen("test.out", "w", stdout); */
int t = 1;
/*cin >> t; */
while (t--) solve();
}
