//
// Created by faisal-saqib on 10:22 AM 1/20/25.
//
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
using namespace std;
const int N=5e3+10;
struct {
int x,y;
char d;
} ship[N];
int main() {
int n;
cin>>n;
for(int i=0;i<n;i++) {
cin>>ship[i].x>>ship[i].y>>ship[i].d;
// ship[i].x=1e9-ship[i].x;
// ship[i].y=1e9-ship[i].y;
}
bool subtask5=0,subtask1=1;
if (subtask1) {
bool alive[n+1]={1};
for (int i=0;i<n;i++)alive[i]=1;
int MX=1e5;
for (int t=1;t<=MX;t++) {
map<pair<int,int>,int>mp;
for (int i=0;i<n;i++) {
if (!alive[i])continue;
if (ship[i].d=='N') {
ship[i].y--;
}else if (ship[i].d=='S') {
ship[i].y++;
}else if (ship[i].d=='E') {
ship[i].x++;
}
else {
ship[i].x++;
}
if (mp.find({ship[i].x,ship[i].y})==mp.end()) {
mp[{ship[i].x,ship[i].y}]=i;
}
else {
alive[i]=0;
alive[mp[{ship[i].x,ship[i].y}]]=0;
}
}
}
for (int i=0;i<n;i++)if(alive[i])cout<<i+1<<endl;;
}
// Subtask 1-5
if (subtask5) {
vector<vector<int>> col;
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
// if(i==j)continue;
if (ship[i].d == 'N' && ship[j].d == 'S') {
if (ship[i].x == ship[j].x && ship[i].y > ship[j].y) {
int time = (ship[i].y - ship[j].y) / 2;
if ((ship[i].y - ship[j].y) % 2 == 0) {
col.push_back({time, i, j});
}
}
} else if (ship[i].d == 'S' && ship[j].d == 'N') {
if (ship[i].x == ship[j].x && ship[i].y < ship[j].y) {
int time = (ship[j].y - ship[i].y) / 2;
if ((ship[j].y - ship[i].y) % 2 == 0) {
col.push_back({time, i, j});
}
}
} else if (ship[i].d == 'E' && ship[j].d == 'W') {
if (ship[i].y == ship[j].y && ship[i].x > ship[j].x) {
int time = (ship[i].x - ship[j].x) / 2;
if ((ship[i].x - ship[j].x) % 2 == 0) {
col.push_back({time, i, j});
}
}
} else if (ship[i].d == 'W' && ship[j].d == 'E') {
if (ship[i].y == ship[j].y && ship[i].x < ship[j].x) {
int time = (ship[j].x - ship[i].x) / 2;
if ((ship[j].x - ship[i].x) % 2 == 0) {
col.push_back({time, i, j});
}
}
} else if (ship[i].d == 'N' && ship[j].d == 'E') {
int dx = ship[j].x - ship[i].x;
int dy = ship[i].y - ship[j].y;
if (dx > 0 && dy > 0 && dx == dy) {
col.push_back({dx, i, j});
}
} else if (ship[i].d == 'E' && ship[j].d == 'N') {
int dx = ship[i].x - ship[j].x;
int dy = ship[j].y - ship[i].y;
if (dx > 0 && dy > 0 && dx == dy) {
col.push_back({dx, i, j});
}
} else if (ship[i].d == 'S' && ship[j].d == 'W') {
int dx = ship[i].x - ship[j].x;
int dy = ship[j].y - ship[i].y;
if (dx > 0 && dy > 0 && dx == dy) {
col.push_back({dx, i, j});
}
} else if (ship[i].d == 'W' && ship[j].d == 'S') {
int dx = ship[j].x - ship[i].x;
int dy = ship[i].y - ship[j].y;
if (dx > 0 && dy > 0 && dx == dy) {
col.push_back({dx, i, j});
}
} //poipopoji
else if (ship[i].d == 'N' && ship[j].d == 'W') {
int dx = ship[i].x - ship[j].x;
int dy = ship[i].y - ship[j].y;
if (dx > 0 && dy > 0 && dx == dy) {
col.push_back({dx, i, j});
}
} else if (ship[i].d == 'W' && ship[j].d == 'N') {
int dx = ship[j].x - ship[i].x;
int dy = ship[j].y - ship[i].y;
if (dx > 0 && dy > 0 && dx == dy) {
col.push_back({dx, i, j});
}
} else if (ship[i].d == 'S' && ship[j].d == 'E') {
int dx = ship[i].x - ship[j].x;
int dy = ship[j].y - ship[i].y;
if (dx > 0 && dy > 0 && dx == dy) {
col.push_back({dx, i, j});
}
} else if (ship[i].d == 'E' && ship[j].d == 'S') {
int dx = ship[j].x - ship[i].x;
int dy = ship[i].y - ship[j].y;
// cout<<"Hola "<<i<<' '<<j<<' '<<dx<<' '<<dy<<endl;
if (dx > 0 && dy > 0 && dx == dy) {
col.push_back({dx, i, j});
}
}
}
}
sort(begin(col),end(col));
// cout<<"ALL collisions:"<<endl;
// for (auto it:col) {
// cout<<it[0]<<' '<<it[1]<<' '<<it[2]<<endl;
// }
// cout<<endl;
bool alive[n+1]={1};
for (int i=0;i<n;i++)alive[i]=1;
for(int i=0;i<col.size();) {
vector<int> dead;
int c=0;
for (int j=i;j<col.size() and col[j][0]==col[i][0];j++) {
// cout<<"Collision "<<col[i][0]<<' '<<col[i][1]<<' '<<col[i][2]<<endl;
if (alive[col[j][1]] && alive[col[j][2]]) {
dead.push_back(col[j][1]);
dead.push_back(col[j][2]);
}
c++;
}
for (int j=0;j<dead.size();j++)alive[dead[j]]=0;
i+=c;
}
vector<int> left;
for (int i=0;i<n;i++)if(alive[i])left.push_back(i);
for (int i=0;i<left.size();i++)cout<<left[i]+1<<endl;
}
}
