#include <bits/stdc++.h>
using namespace std;
#define col tuple<int, int, int>
const tuple<int, int, int> NTP = make_tuple(-1, 0, 0);
int n;
vector<map<int, map<int, int>>> rows(16);
vector<int> dirmap = {0, 1, 2, 1, -1, 0, 1, 2, -2, -1, 0, -1, -1, -2, 1, 0};
vector<tuple<int, int, int>> ships;
col get_collision(int shipid, int dir) {
int x, y, d;
tie(x, y, d) = ships[shipid];
int dirid = 4 * d + dir;
if(dirmap[dirid] == 0) return NTP;
//cout << dirid << " " << x << "\n";
if(dirmap[dirid] == 1) {
int posid = ((d ^ 0x1) == dir) ? x + y : x - y;
auto it = rows[dirid][posid].upper_bound(x);
if(it == rows[dirid][posid].end()) return NTP;
//cout << "COLLISION: " << shipid << " " << it->second << "\n";
return make_tuple(abs(x - it->first), shipid, it->second);
}
if(dirmap[dirid] == -1) {
int posid = ((d ^ 0x1) == dir) ? x + y : x - y;
auto it = rows[dirid][posid].lower_bound(x);
if(it == rows[dirid][posid].begin()) return NTP;
--it;
//cout << "COLLISION: " << shipid << " " << it->second << " " << d << " " << dir << "\n";
return make_tuple(abs(x - it->first), shipid, it->second);
}
return NTP;
}
int main() {
cin >> n;
for(int i = 0; i < n; i++) {
int x, y;
char ch;
cin >> x >> y >> ch;
int dir = 0;
if(ch == 'N' || ch == 'W') dir |= 2;
if(ch == 'S' || ch == 'N') dir |= 1;
//cout << dir << " " << dir + 4 * (dir ^ 0x1) << "\n";
rows[dir + 4 * (dir ^ 0x1)][x + y][x] = i;
rows[dir + 4 * (3 - dir)][x - y][x] = i;
if(dir & 0x1)
rows[dir + 4 * (dir ^ 0x2)][x][y] = i;
else
rows[dir + 4 * (dir ^ 0x2)][y][x] = i;
ships.push_back(make_tuple(x, y, dir));
}
/*
for(int i = 0; i < 16; i++) {
cout << "i: " << i << "\n";
for(pair<int, map<int, int>> p : rows[i]) {
cout << p.first << "\n";
}
}
*/
vector<bool> alive(n, true);
priority_queue<col, vector<col>, greater<col>> q;
for(int i = 0; i < n; i++) {
for(int j = 0; j < 4; j++) {
col c = get_collision(i, j);
if(c == NTP) continue;
//cout << "A";
q.push(c);
}
}
int lastt = -1;
vector<int> to_remove;
while(!q.empty()) {
assert(q.size() < 1e6);
if(get<0>(q.top()) != lastt) {
for(int a : to_remove) {
alive[a] = false;
int x, y, dir;
tie(x, y, dir) = ships[a];
rows[dir + 4 * (dir ^ 0x1)][x + y].erase(x);
rows[dir + 4 * (3 - dir)][x - y].erase(x);
if(dir & 0x1)
rows[dir + 4 * (dir ^ 0x2)][x].erase(y);
else
rows[dir + 4 * (dir ^ 0x2)][y].erase(x);
}
lastt = get<0>(q.top());
}
int t, id1, id2;
tie(t, id1, id2) = q.top();
q.pop();
//cout << "Q: " << t << " " << id1 << " " << id2 << "\n";
if(alive[id1] && alive[id2]) {
//cout << "\tX\n";
to_remove.push_back(id1);
to_remove.push_back(id2);
}
else if(alive[id1]) {
col c = get_collision(id1, get<2>(ships[id2]));
if(c != NTP) q.push(c);
to_remove.push_back(id1);
}
else if(alive[id2]) {
col c = get_collision(id2, get<2>(ships[id1]));
if(c != NTP) q.push(c);
to_remove.push_back(id2);
}
}
for(int a : to_remove) {
alive[a] = false;
}
for(int i = 0; i < n; i++) {
if(alive[i]) cout << i + 1 << "\n";
}
return 0;
}
