#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define all(x) x.begin(), x.end()
#define int long long
/*
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;*/
using namespace std;
const int N = 2e5 + 42;
struct Point {
int x, y, i, type;
};
//NSEW
int dl[] = {0, 0, 1, -1},
dc[] = {-1, 1, 0, 0};
int dirl[] = {-2, -1, 0, 1, 2, 1, 0, -1},
dirc[] = {0, 1, 2, 1, 0, -1, -2, -1};
int corr[4][8] = {{0, 0, 0, 0, 0, 0, 0, 0},
{0, 1, 0, 1, 0, 1, 0, 1},
{1, 0, 1, 1, 1, 0, 1, 1},
{1, 1, 1, 0, 1, 1, 1, 0}};
Point pt[N];
bool mort[N], bourr[N];
int n, nxt[N][8];
struct Pair {
int i, j, dist;
bool operator <(const Pair& other) const {
return dist > other.dist;
}
};
priority_queue<Pair> pq;
void create(int a, int b) {
if(a != b && a != -1 && b != -1 && !mort[a] && !mort[b]) {
Point p = pt[a], q = pt[b];
int dist = (abs(p.x - q.x) + abs(p.y - q.y))/2;
if(p.x + dist * dl[p.type] == q.x + dist * dl[q.type] && p.y + dist * dc[p.type] == q.y + dist * dc[q.type])
pq.push({a, b, dist});
}
}
void del(int i) {
if(mort[i]) return;
mort[i] = true;
for(int iDir = 0; iDir < 8; iDir++) {
for(int t = 0; t < 4; t++) if(nxt[i][iDir] != -1) {
nxt[nxt[i][iDir]][iDir ^ 4] = nxt[i][iDir ^ 4];
int a = nxt[i][iDir], b = nxt[i][iDir ^ 4];
create(a, b);
}
}
}
void init() {
for(int i = 0; i < n; i++)
mort[i] = false;
for(int i = 0; i < n; i++)
for(int iDir = 0; iDir < 8; iDir++)
nxt[i][iDir] = -1;
}
void readInput() {
cin >> n;
map<char, int> cor;
cor['N'] = 0, cor['S'] = 1, cor['E'] = 2, cor['W'] = 3;
for(int i = 0; i < n; i++) {
pt[i].i = i;
cin >> pt[i].x >> pt[i].y;
char c; cin >> c;
pt[i].type = cor[c];
}
}
void solve() {
readInput();
init();
vector<pair<int, int>> pot;
for(int iDir = 0; iDir < 8; iDir++) {
sort(pt, pt + n,
[=](Point a, Point b) {
return a.x * dirc[iDir] - a.y * dirl[iDir] < b.x * dirc[iDir] - b.y * dirl[iDir];
});
map<int, int> pre[2];
for(int i = 0; i < n; i++) {
int proj = pt[i].x * dirl[iDir] + pt[i].y * dirc[iDir];
if(pre[corr[pt[i].type][iDir]].count(proj)) {
nxt[pt[i].i][iDir] = pre[corr[pt[i].type][iDir]][proj];
pot.push_back({pt[i].i, nxt[pt[i].i][iDir]});
}
pre[corr[pt[i].type][iDir]][proj] = pt[i].i;
}
}
sort(pt, pt + n,
[](Point a, Point b) {
return a.i < b.i;
});
for(auto [a, b] : pot) create(a, b);
while(!pq.empty()) {
int dist = pq.top().dist;
vector<int> suppr;
while(!pq.empty() && pq.top().dist == dist) {
int a = pq.top().i, b = pq.top().j;
if(!mort[a] && !mort[b]) {
suppr.push_back(a);
suppr.push_back(b);
}
pq.pop();
}
for(int i : suppr)
if(!mort[i])
del(i);
}
for(int i = 0; i < n; i++)
if(!mort[i]) cout << i+1 << ' ';
cout << '\n';
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
solve();
}
