#include<bits/stdc++.h>
#define ll long long
#define ldb long double
#define db double
#define fi first
#define se second
#define sza(a) (int)a.size()
#define pir pair<int,int>
#define pirll pair<ll,ll>
using namespace std;
const int maxn = 2e5 + 5;
struct CTDL{
int x = 0,y = 0,direction = 0,id = 0;
};
CTDL a[maxn];
void move_ship(CTDL &t){
if (t.direction == 0) t.y--;
if (t.direction == 1) t.x++;
if (t.direction == 2) t.y++;
if (t.direction == 3) t.x--;
}
int get_direction(const char &c){
if (c == 'N') return 0;
if (c == 'E') return 1;
if (c == 'S') return 2;
return 3;
}
void input(int n){
for (int i = 1 ; i <= n ; i++){
cin >> a[i].x >> a[i].y;
a[i].id = i;
char c;
cin >> c;
a[i].direction = get_direction(c);
}
}
int collide(CTDL s1,CTDL s2){
if (s1.direction > s2.direction) swap(s1,s2);
int x1 = s1.x,y1 = s1.y,d1 = s1.direction,x2 = s2.x,y2 = s2.y,d2 = s2.direction;
if (d1 == d2) return -1;
//N-E collision
if (d1 == 0 && d2 == 1){
if (x1 < x2 || y1 < y2) return -1;
if (y1 - y2 == x1 - x2) return x1 - x2;
return -1;
}
//N-S collision
if (d1 == 0 && d2 == 2){
if (x1 != x2 || y1 < y2 || (y1 - y2) % 2) return -1;
return (y1 - y2)/2;
}
//N-W collision
if (d1 == 0 && d2 == 3){
if (x1 > x2 || y1 < y2) return -1;
if (y1 - y2 == x2 - x1) return y1 - y2;
return -1;
}
//E-S collision
if (d1 == 1 && d2 == 2){
if (x1 > x2 || y1 < y2) return -1;
if (y1 - y2 == x2 - x1) return y1 - y2;
return -1;
}
//E-W collision
if (d1 == 1 && d2 == 3){
if (y1 != y2 || x1 > x2 || (x2 - x1) % 2) return -1;
return (x2 - x1)/2;
}
//S-W collision
if (d1 == 2 && d2 == 3){
if (x1 > x2 || y1 > y2) return -1;
if (y2 - y1 != x2 - x1) return -1;
return x2 - x1;
}
return -1;
}
namespace subtask_3_4_5{
bool subtask_3_4_5(int n){
return (n <= 5000);
}
bool deleted[maxn];
vector <pair<int,pir>> collision;
void generate_collision(int n){
for (int i = 1 ; i <= n ; i++)
for (int j = i + 1 ; j <= n ; j++){
int t = collide(a[i],a[j]);
if (t > -1)
collision.push_back({t,{i,j}});
}
}
void ship_solve(int n){
generate_collision(n);
sort(collision.begin(),collision.end());
int p = 0,N = collision.size();
while (p < N){
int nxt = p;
while (nxt < N && collision[p].fi == collision[nxt].fi) nxt++;
vector <int> to_delete;
for (int i = p ; i < nxt ; i++){
int u = collision[i].se.fi,v = collision[i].se.se;
if (deleted[u] || deleted[v]) continue;
if (u == 20 || v == 20) cerr << u << " " << v << " " << collision[p].fi << endl;
to_delete.push_back(u);
to_delete.push_back(v);
}
for (int u : to_delete)
deleted[u] = 1;
p = nxt;
}
}
void solve(int n){
ship_solve(n);
for (int i = 1 ; i <= n ; i++)
if (!deleted[i]) cout << i << "\n";
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
// freopen("NAVAL.inp","r",stdin);
// freopen("NAVAL.out","w",stdout);
int n;
cin >> n;
input(n);
subtask_3_4_5::solve(n);
return 0;
}
