#include <bits/stdc++.h>
using namespace std;
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)
#define foreach(it, c) for (auto it = begin(c); it != end(c); it++)
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vb = vector<bool>;
using vll = vector<ll>;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
#define fst first
#define snd second
#define pb push_back
#define eb emplace_back
const ll INF = 1e18;
struct ship {
ll x, y;
int id;
char dir;
};
struct colission {
int i, j; ll t;
bool operator<(const colission &o) const {
return t > o.t;
}
};
int id(char dir) {
if (dir == 'N') return 0;
if (dir == 'S') return 1;
if (dir == 'E') return 2;
if (dir == 'W') return 3;
assert(false);
}
int dx[] = {0, 0, 1, -1};
int dy[] = {-1, 1, 0, 0};
using info = optional<pair<list<ship>::iterator, ll>>;
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n;
cin >> n;
vector<ship> s(n);
forn(i, n) {
cin >> s[i].x >> s[i].y >> s[i].dir;
s[i].id = i;
}
map<ll, list<ship>> NS, NE, NW, SE, SW, EW;
/* NS
* x1 = x2
* y1 - t = y2 + t => y1 - y2 = 2 * t */
/* NE
* x1 = x2 + t => t = x1 - x2
* y1 - t = y2 => t = y1 - y2
* => x1 - x2 = y1 - y2 => x1 - y1 = x2 - y2 */
/* NW
* x1 = x2 - t => t = x2 - x1
* y1 - t = y2 => t = y1 - y2
* => x2 - x1 = y1 - y2 => x2 + y2 = x1 + y1 */
/* SE
* x1 = x2 + t => t = x1 - x2
* y1 + t = y2 => t = y2 - y1
* => x1 - x2 = y2 - y1 => x1 + y1 = x2 + y2 */
/* SW
* x1 = x2 - t => t = x2 - x1
* y1 + t = y2 => t = y2 - y1
* x2 - x1 = y2 - y1 => x2 - y2 = x1 - y1 */
/* EW
* x1 + t = x2 - t => 2 * t = x2 - x1
* y1 = y2 */
forn(i, n) {
if (s[i].dir == 'N') {
NS[s[i].x].pb(s[i]);
NE[s[i].x - s[i].y].pb(s[i]);
NW[s[i].x + s[i].y].pb(s[i]);
} else if (s[i].dir == 'S') {
NS[s[i].x].pb(s[i]);
SE[s[i].x + s[i].y].pb(s[i]);
SW[s[i].x - s[i].y].pb(s[i]);
} else if (s[i].dir == 'E') {
NE[s[i].x - s[i].y].pb(s[i]);
SE[s[i].x + s[i].y].pb(s[i]);
EW[s[i].y].pb(s[i]);
} else if (s[i].dir == 'W') {
NW[s[i].x + s[i].y].pb(s[i]);
SW[s[i].x - s[i].y].pb(s[i]);
EW[s[i].y].pb(s[i]);
} else {
assert(false);
}
}
auto cmpX = [&](const ship &lhs, const ship &rhs) {
return lhs.x < rhs.x;
};
auto cmpY = [&](const ship &lhs, const ship &rhs) {
return lhs.y < rhs.y;
};
auto sortAll = [&](map<ll, list<ship>> &m, auto cmp) {
for (auto &[_, l] : m) {
vector<ship> v(all(l));
sort(all(v), cmp);
l = list<ship>(all(v));
}
};
sortAll(NS, cmpY);
sortAll(NE, cmpX);
sortAll(NW, cmpX);
sortAll(SE, cmpY);
sortAll(SW, cmpY);
sortAll(EW, cmpX);
vector<info> whereNS, whereNE, whereNW, whereSE, whereSW, whereEW;
auto getWhere = [&](map<ll, list<ship>> &m, vector<info> &where) {
where.assign(n, nullopt);
for (auto &[val, l] : m) foreach(it, l) where[it->id] = {it, val};
};
getWhere(NS, whereNS);
getWhere(NE, whereNE);
getWhere(NW, whereNW);
getWhere(SE, whereSE);
getWhere(SW, whereSW);
getWhere(EW, whereEW);
priority_queue<colission> pq;
auto add = [&](const ship &a, const ship &b) {
if (a.dir == b.dir) return;
ll t;
if (dx[id(b.dir)] - dx[id(a.dir)] != 0) {
t = (a.x - b.x) / (dx[id(b.dir)] - dx[id(a.dir)]);
} else {
assert(dy[id(b.dir)] - dy[id(a.dir)] != 0);
t = (a.y - b.y) / (dy[id(b.dir)] - dy[id(a.dir)]);
}
assert(a.x + dx[id(a.dir)] * t == b.x + dx[id(b.dir)] * t);
assert(a.y + dy[id(a.dir)] * t == b.y + dy[id(b.dir)] * t);
if (t > 0) {
colission c;
c.i = a.id, c.j = b.id, c.t = t;
pq.push(c);
}
};
auto addAll = [&](map<ll, list<ship>> &m) {
for (auto &[_, l] : m) foreach(it, l) {
if (next(it) != end(l)) add(*it, *next(it));
}
};
addAll(NS);
addAll(NE);
addAll(NW);
addAll(SE);
addAll(SW);
addAll(EW);
vll time(n, INF);
vector<bool> done(n, false);
auto erase = [&](int i, vector<info> &where, map<ll, list<ship>> &m) {
if (!where[i].has_value()) return;
auto [it, val] = where[i].value();
list<ship> &l = m[val];
if (it == end(l)) return;
if (it != begin(l)) {
auto prv = prev(it);
auto nxt = next(it);
if (nxt != end(l)) add(*prv, *nxt);
}
l.erase(it);
where[i] = nullopt;
};
auto eraseAll = [&](int i) {
if (done[i]) return;
done[i] = true;
erase(i, whereNS, NS);
erase(i, whereNE, NE);
erase(i, whereNW, NW);
erase(i, whereSE, SE);
erase(i, whereSW, SW);
erase(i, whereEW, EW);
};
while (!pq.empty()) {
colission c = pq.top();
pq.pop();
if (time[c.i] >= c.t && time[c.j] >= c.t) {
time[c.i] = c.t, time[c.j] = c.t;
eraseAll(c.i), eraseAll(c.j);
}
}
forn(i, n) if (!done[i]) {
cout << i + 1 << '\n';
}
return 0;
}
