#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define pt complex<int>
const int INF = 1e18;
struct Event{
int len;
int lship_id, rship_id;
int dim_id, dim_pos;
bool operator<(const Event& b)const{
if(len != b.len){
return len<b.len;
}
if(lship_id != b.lship_id){
return lship_id < b.lship_id;
}
if(rship_id != b.rship_id){
return rship_id < b.rship_id;
}
if(dim_id != b.dim_id){
return dim_id < b.dim_id;
}
return dim_pos < b.dim_pos;
}
};
struct Ship{
int id;
pt pos;
int dist_right = -1;
char dir_letter;
bool operator<(const Ship& b)const{
return false;
}
};
set<Event> lens;
struct Line{
int dim_id, dim_pos;
list<pair<int, Ship>> ships;
unordered_map<int, list<pair<int, Ship>>::iterator> m;
char go_left, go_right;
void insert_event(list<pair<int, Ship>>::iterator a, list<pair<int, Ship>>::iterator b){
lens.insert(Event{Event{b->first-a->first, a->second.id, b->second.id, dim_id, dim_pos}});
}
void erase_event(list<pair<int, Ship>>::iterator a, list<pair<int, Ship>>::iterator b){
lens.erase(Event{Event{b->first-a->first, a->second.id, b->second.id, dim_id, dim_pos}});
}
void make_pair(list<pair<int, Ship>>::iterator a, list<pair<int, Ship>>::iterator b){
if(b== ships.end()){
return;
}
if(a->second.dir_letter == go_right){
if(b->second.dir_letter == go_left){
a->second.dist_right = b->first-a->first;
insert_event(a, b);
}
}
}
void unmake_pair(list<pair<int, Ship>>::iterator a, list<pair<int, Ship>>::iterator b){
if(b== ships.end()){
return;
}
if(a->second.dir_letter == go_right){
if(b->second.dir_letter == go_left){
a->second.dist_right = -1;
erase_event(a, b);
}
}
}
void build(vector<pair<int, Ship>> elems, char go_right_dir, char go_left_dir){
go_right = go_right_dir;
go_left= go_left_dir;
sort(elems.begin(), elems.end());
ships = list<pair<int, Ship>>(elems.begin(), elems.end());
auto it = ships.begin();
for(; it!=ships.end();){
if(it->second.dir_letter != go_right_dir && it->second.dir_letter != go_left_dir){
it = ships.erase(it);
}
else{
++it;
}
}
it = ships.begin();
for(; it!=ships.end(); ++it){
m[it->second.id]= it;
auto next= it;
++next;
make_pair(it, next);
}
}
void erase(list<pair<int, Ship>>::iterator it){
if(it!=ships.begin()){
auto prev = it;
--prev;
unmake_pair(prev, it);
}
if(it != ships.end()){
auto next= it;
++next;
unmake_pair(it, next);
}
auto next = ships.erase(it);
if(next!=ships.begin()){
auto prev= next;
--prev;
make_pair(prev, next);
}
}
void erase(int ship_id){
if(m.find(ship_id) == m.end()){
return;
}
erase(m[ship_id]);
m.erase(ship_id);
}
};
vector<char> go_right = {'E', 'S', 'E', 'N', 'E', 'S'};
vector<char> go_left = {'W', 'N', 'S', 'W', 'N', 'W'};
vector<pt> coef_orth = {{0, 1}, {1, 0}, {1, 1}, {1, 1}, {1, -1}, {1, -1}};
vector<pt> coef_col = {{1, 0}, {0, 1}, {1, -1}, {1, -1}, {1, 1}, {1, 1}};
int dot(pt a, pt b){
return (a*conj(b)).real();
}
pii get_pos(Ship s, int dim){
return {dot(s.pos,coef_orth[dim]), dot(s.pos, coef_col[dim])};
}
vector<Ship> ships;
int N;
signed main(){
cin>>N;
for(int i = 0; i<N; i++){
pii pos;
cin>>pos.first>>pos.second;
char dir;
cin>>dir;
ships.push_back(Ship{i, {pos.first, pos.second},-1, dir});
}
vector<unordered_map<int, Line>> dims(6);
vector<vector<pii>> ship_coords(6, vector<pii> (N));
for(int dim = 0; dim<6; dim++){
unordered_map<int, vector<pair<int, Ship>>> categorized;
for(auto ship: ships){
pii dim_coord = get_pos(ship, dim);
categorized[dim_coord.first].push_back({dim_coord.second, ship});
ship_coords[dim][ship.id] = dim_coord;
}
for(auto e: categorized){
dims[dim][e.first].dim_id = dim;
dims[dim][e.first].dim_pos = e.first;
dims[dim][e.first].build(e.second, go_right[dim], go_left[dim]);
}
}
set<int> alive;
for(int i = 0; i<N; i++){
alive.insert(i);
}
while(lens.size()>0){
int t= lens.begin()->len;
vector<Event> cur_events;
auto it= lens.begin();
while(it!=lens.end() && it->len == t){
cur_events.push_back(*it);
++it;
}
for(auto e: cur_events){
vector<int> to_remove = {e.lship_id, e.rship_id};
for(auto rem: to_remove){
alive.erase(rem);
for(int dim = 0; dim<6; dim++){
int dim_pos = ship_coords[dim][rem].first;
dims[dim][dim_pos].erase(rem);
}
}
}
}
for(auto e: alive){
cout<<e+1<<endl;
}
}
