#include <bits/stdc++.h>
using namespace std;
bool ty(char c)
{
return c=='N' or c=='S';
}
int coll(int x,int y,char c,int x1,int y1,char c1)
{
if (c==c1) return -1;
if (ty(c)==ty(c1))
{
if (ty(c))
{
if (c1=='N')
swap(y,y1);
if (x==x1 && y>y1)
return (y-y1)/2;
return -1;
}
else
{
if (c1=='E')
swap(x,x1);
if (y==y1 && x<x1)
return (x1-x)/2;
return -1;
}
}
if (ty(c1))
swap(x,x1),swap(y,y1),swap(c,c1);
if (c=='N')
{
if(c1=='E' && x1<x && x-y==x1-y1)
return x-x1;
else if(c1=='W' && x1>x && x+y==x1+y1)
return x1-x;
}
else if(c=='S')
{
if(c1=='E' && x1<x && x+y==x1+y1)
return x-x1;
else if(c1=='W' && x<x1 && x-y==x1-y1)
return x1-x;
}
return -1;
}
int main()
{
int n;
cin>>n;
if (n<=5000)
{
int x[n],y[n];
char c[n];
for (int i=0;i<n;i++)
cin>>x[i]>>y[i]>>c[i];
map<int,vector<pair<int,int>>> edg;
for (int i=0;i<n;i++)
for (int j=i+1;j<n;j++)
{
int w=coll(x[i],y[i],c[i],x[j],y[j],c[j]);
if (~w)
edg[w].push_back({i,j});
}
bool det[n]={};
for (auto [t,v]:edg)
{
set<int> se;
for (auto [i,j]:v)
if (!det[i] && !det[j])
se.insert(i),se.insert(j);
for (int i:se)
det[i]=1;
}
for (int i=0;i<n;i++)
if (!det[i])
cout<<i+1<<endl;
}
else
{
map<int,vector<vector<int>>> se;
int x,y;
char c;
for (int i=0;i<n;i++)
{
cin>>x>>y>>c;
se[x+y].push_back({x,i+1,ty(c)});
}
vector<int> ans;
for (auto [w,v]:se)
{
sort(v.begin(),v.end());
int l=0;
vector<pair<int,int>> rn;
for (int i=1;i<v.size();i++)
if (v[l][2]!=v[i][2])
rn.push_back({l,i}),l=i;
rn.push_back({l,n});
int st=v[0][2];
for (int i=st;i+1<rn.size();i+=2)
{
while (rn[i].first<rn[i].second && rn[i+1].first<rn[i+1].second)
rn[i].second--,rn[i+1].first++;
for (int j=rn[i].first;j<rn[i].second;j++)
ans.push_back(v[j][1]);
for (int j=rn[i+1].first;j<rn[i+1].second;j++)
ans.push_back(v[j][1]);
}
}
for (int i:ans)
cout<<i<<' ';
cout<<endl;
}
return 0;
}
