#include <bits/stdc++.h>
using namespace std;
struct ship{
int x;
int y;
int i;
char c;
};
bool comp(const ship &a, const ship &b){
if(a.x==b.x){
return a.y<b.y;
}
return a.x<b.x;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
ship arr[n];
for(int i = 0;i<n;i++){
cin >> arr[i].x;
cin >> arr[i].y;
cin >> arr[i].c;
arr[i].i=i;
}
map<int,vector<ship>>sn1,sn2,en,nw,es,sw,ew1,ew2;
//ns and ew require same mod2 also.
//{x,x-y,x+y,x+y,x-y,y}
for(int i = 0;i<n;i++){
if(arr[i].c=='N'){
if(arr[i].x%2){
sn1[arr[i].x].push_back(arr[i]);
}
else{
sn2[arr[i].x].push_back(arr[i]);
}
en[arr[i].x-arr[i].y].push_back(arr[i]);
nw[arr[i].x+arr[i].y].push_back(arr[i]);
}
else if(arr[i].c=='S'){
if(arr[i].x%2){
sn1[arr[i].x].push_back(arr[i]);
}
else{
sn2[arr[i].x].push_back(arr[i]);
}
es[arr[i].x+arr[i].y].push_back(arr[i]);
sw[arr[i].x-arr[i].y].push_back(arr[i]);
}
else if(arr[i].c=='W'){
nw[arr[i].x+arr[i].y].push_back(arr[i]);
sw[arr[i].x-arr[i].y].push_back(arr[i]);
if(arr[i].y%2){
ew1[arr[i].y].push_back(arr[i]);
}
else{
ew2[arr[i].y].push_back(arr[i]);
}
}
else if(arr[i].c=='E'){
en[arr[i].x-arr[i].y].push_back(arr[i]);
es[arr[i].x+arr[i].y].push_back(arr[i]);
if(arr[i].y%2){
ew1[arr[i].y].push_back(arr[i]);
}
else{
ew2[arr[i].y].push_back(arr[i]);
}
}
}
for(pair<int,vector<ship>> p : sn1){
sort(sn1[p.first].begin(),sn1[p.first].end(),comp);
}
for(pair<int,vector<ship>> p : sn2){
sort(sn2[p.first].begin(),sn2[p.first].end(),comp);
}
for(pair<int,vector<ship>> p : en){
sort(en[p.first].begin(),en[p.first].end(),comp);
}
for(pair<int,vector<ship>> p : nw){
sort(nw[p.first].begin(),nw[p.first].end(),comp);
}
for(pair<int,vector<ship>> p : es){
sort(es[p.first].begin(),es[p.first].end(),comp);
}
for(pair<int,vector<ship>> p : sw){
sort(sw[p.first].begin(),sw[p.first].end(),comp);
}
for(pair<int,vector<ship>> p : ew1){
sort(ew1[p.first].begin(),ew1[p.first].end(),comp);
}
for(pair<int,vector<ship>> p : ew2){
sort(ew2[p.first].begin(),ew2[p.first].end(),comp);
}
priority_queue<array<int,5>,vector<array<int,5>>,greater<array<int,5>>>pq;
//{time,type,index1,index2,group}
//index1<index2;
auto dist = [&] (ship a, ship b){
return abs(a.x-b.x)+abs(a.y-b.y);
};
for(pair<int,vector<ship>> p : sn1){
for(int i = 1;i<p.second.size();i++){
if(p.second[i-1].c=='S'&&p.second[i].c=='N'){
//EVENT push to queue
pq.push({dist(p.second[i],p.second[i-1])/2,1,i-1,i,p.first});
}
}
}
for(pair<int,vector<ship>> p : sn2){
for(int i = 1;i<p.second.size();i++){
if(p.second[i-1].c=='S'&&p.second[i].c=='N'){
//EVENT push to queue
pq.push({dist(p.second[i],p.second[i-1])/2,2,i-1,i,p.first});
}
}
}
for(pair<int,vector<ship>> p : en){
for(int i = 1;i<p.second.size();i++){
if(p.second[i-1].c=='E'&&p.second[i].c=='N'){
//EVENT push to queue
pq.push({dist(p.second[i],p.second[i-1])/2,3,i-1,i,p.first});
}
}
}
for(pair<int,vector<ship>> p : nw){
for(int i = 1;i<p.second.size();i++){
if(p.second[i-1].c=='N'&&p.second[i].c=='W'){
//EVENT push to queue
pq.push({dist(p.second[i],p.second[i-1])/2,4,i-1,i,p.first});
}
}
}
for(pair<int,vector<ship>> p : es){
for(int i = 1;i<p.second.size();i++){
if(p.second[i-1].c=='E'&&p.second[i].c=='S'){
//EVENT push to queue
pq.push({dist(p.second[i],p.second[i-1])/2,5,i-1,i,p.first});
}
}
}
for(pair<int,vector<ship>> p : sw){
for(int i = 1;i<p.second.size();i++){
if(p.second[i-1].c=='S'&&p.second[i].c=='W'){
//EVENT push to queue
pq.push({dist(p.second[i],p.second[i-1])/2,6,i-1,i,p.first});
}
}
}
for(pair<int,vector<ship>> p : ew1){
for(int i = 1;i<p.second.size();i++){
if(p.second[i-1].c=='E'&&p.second[i].c=='W'){
//EVENT push to queue
pq.push({dist(p.second[i],p.second[i-1])/2,7,i-1,i,p.first});
}
}
}
for(pair<int,vector<ship>> p : ew2){
for(int i = 1;i<p.second.size();i++){
if(p.second[i-1].c=='E'&&p.second[i].c=='W'){
//EVENT push to queue
pq.push({dist(p.second[i],p.second[i-1])/2,8,i-1,i,p.first});
}
}
}
//priority_queue filled with initial
int des[n];
fill(des,des+n,2e9);
auto coll = [&] (map<int,vector<ship>>&mp, char prev, char nx) {
//mp
auto [time,type,ind1,ind2,group] = pq.top();
pq.pop();
ship a = mp[group][ind1];
ship b = mp[group][ind2];
if(min(des[a.i],des[b.i])<time){
//one was destroyed earlier so nothing happens(for now)
if(des[a.i]<time){
//a was destroyed so decrement ind1
while(ind1>=0&&des[mp[group][ind1].i]<time){
ind1--;
}
if(ind1>=0){
if(mp[group][ind1].c==prev){
//valid
a=mp[group][ind1];
pq.push({dist(a,b)/2,type,ind1,ind2,group});
}
}
}
else{
//move ind2
while(ind2<mp[group].size()&&des[mp[group][ind2].i]<time){
ind2++;
}
if(ind2<mp[group].size()){
if(mp[group][ind2].c==nx){
//valid
b=mp[group][ind2];
pq.push({dist(b,a)/2,type,ind1,ind2,group});
}
}
}
}
else{
//collision
des[a.i]=time;
des[b.i]=time;
//now must push new collision due to this also
ind1--;
ind2++;
while(ind2<mp[group].size()&&des[mp[group][ind2].i]<time){
ind2++;
}
while(ind1>=0&&des[mp[group][ind1].i]<time){
ind1--;
}
if(ind2<mp[group].size()){
if(mp[group][ind2].c==nx){
if(ind1>=0){
if(mp[group][ind1].c==prev){
//valid
a=mp[group][ind1];
b=mp[group][ind2];
pq.push({dist(a,b)/2,type,ind1,ind2,group});
}
}
}
}
}
};
while(!pq.empty()){
auto [time,type,ind1,ind2,group] = pq.top();
//sn1,sn2,en,nw,es,sw,ew1,ew2;
if(type==1){
coll(sn1,'S','N');
}
else if(type==2){
coll(sn2,'S','N');
}
else if(type==3){
coll(en,'E','N');
}
else if(type==4){
coll(nw,'N','W');
}
else if(type==5){
coll(es,'E','S');
}
else if(type==6){
coll(sw,'S','W');
}
else if(type==7){
coll(ew1,'E','W');
}
else {
coll(ew2,'E','W');
}
}
for(int i = 0;i<n;i++){
if(des[i]==2e9){
cout << i+1 << "\n";
}
}
return 0;
}
