#include <bits/stdc++.h>
using namespace std;
const int nmax = 2e5;
struct punct
{
int x, y;
char dir;
};
int n;
punct v[nmax + 5];
int sel[nmax + 5];
int cnt;
priority_queue<pair<int,pair<int,int>>, vector<pair<int,pair<int,int>>>, greater<pair<int,pair<int,int>>>> h;
struct diag
{
bool is_built;
multiset<pair<int,pair<int,int>>> s;
void add(int i, int x, int tip)
{
s.insert({x, {tip, i}});
}
void build()
{
if(is_built)
{
return;
}
is_built = true;
int last = 0;
int last_x = 0;
int last_tip = -1;
for(auto it=s.begin();it!=s.end();it++)
{
if(last_tip == 0 && it -> second.first == 1)
{
h.push({it->first - last_x, {last, it->second.second}});
}
last = it->second.second;
last_x = it->first;
last_tip = it->second.first;
}
}
void rem(int i, int x, int tip)
{
auto er = s.lower_bound({x, {tip, i}});
auto u = s.upper_bound({x, {tip, i}});
if(er != s.begin() && u != s.end())
{
auto p = er;
p--;
if(p -> second.first == 0 && u -> second.first == 1)
{
h.push({u->first - p->first, {p->second.second, u->second.second}});
}
}
s.erase(er);
}
};
diag dne[nmax + 5], dnv[nmax + 5], dse[nmax + 5], dsv[nmax + 5], dns[nmax + 5], dve[nmax + 5];
vector<int> d0, d1;
vector<int> dx, dy;
int get_val(vector<int> &a, int val)
{
int st = 1;
int dr = a.size();
int poz = 0;
while(st <= dr)
{
int mij = (st + dr) >> 1;
if(a[mij - 1] <= val)
{
poz = mij;
st = mij + 1;
}
else
{
dr = mij - 1;
}
}
return poz;
}
void Add(int i)
{
int diag0 = get_val(d0, v[i].x - v[i].y);
int diag1 = get_val(d1, v[i].x + v[i].y);
if(v[i].dir == 'N')
{
dne[diag0].add(i, v[i].x, 1);
dnv[diag1].add(i, v[i].x, 0);
}
else if(v[i].dir == 'S')
{
dsv[diag0].add(i, v[i].x, 0);
dse[diag1].add(i, v[i].x, 1);
}
else if(v[i].dir == 'E')
{
dne[diag0].add(i, v[i].x, 0);
dse[diag1].add(i, v[i].x, 0);
}
else if(v[i].dir == 'W')
{
dsv[diag0].add(i, v[i].x, 1);
dnv[diag1].add(i, v[i].x, 1);
}
int px = get_val(dx, v[i].x);
int py = get_val(dy, v[i].y);
if(v[i].dir == 'N')
{
dns[px].add(i, v[i].y / 2, 1);
}
else if(v[i].dir == 'S')
{
dns[px].add(i, v[i].y / 2, 0);
}
else if(v[i].dir == 'E')
{
dve[py].add(i, v[i].x / 2, 0);
}
else if(v[i].dir == 'W')
{
dve[py].add(i, v[i].x / 2, 1);
}
}
void Build(int i)
{
int diag0 = get_val(d0, v[i].x - v[i].y);
int diag1 = get_val(d1, v[i].x + v[i].y);
if(v[i].dir == 'N')
{
dne[diag0].build();
dnv[diag1].build();
}
else if(v[i].dir == 'S')
{
dsv[diag0].build();
dse[diag1].build();
}
else if(v[i].dir == 'E')
{
dne[diag0].build();
dse[diag1].build();
}
else if(v[i].dir == 'W')
{
dsv[diag0].build();
dnv[diag1].build();
}
int px = get_val(dx, v[i].x);
int py = get_val(dy, v[i].y);
if(v[i].dir == 'N')
{
dns[px].build();
}
else if(v[i].dir == 'S')
{
dns[px].build();
}
else if(v[i].dir == 'E')
{
dve[py].build();
}
else if(v[i].dir == 'W')
{
dve[py].build();
}
}
void Remove(int i)
{
if(sel[i])
{
return;
}
sel[i] = cnt;
int diag0 = get_val(d0, v[i].x - v[i].y);
int diag1 = get_val(d1, v[i].x + v[i].y);
if(v[i].dir == 'N')
{
dne[diag0].rem(i, v[i].x, 1);
dnv[diag1].rem(i, v[i].x, 0);
}
else if(v[i].dir == 'S')
{
dsv[diag0].rem(i, v[i].x, 0);
dse[diag1].rem(i, v[i].x, 1);
}
else if(v[i].dir == 'E')
{
dne[diag0].rem(i, v[i].x, 0);
dse[diag1].rem(i, v[i].x, 0);
}
else if(v[i].dir == 'W')
{
dsv[diag0].rem(i, v[i].x, 1);
dnv[diag1].rem(i, v[i].x, 1);
}
int px = get_val(dx, v[i].x);
int py = get_val(dy, v[i].y);
if(v[i].dir == 'N')
{
dns[px].rem(i, v[i].y / 2, 1);
}
else if(v[i].dir == 'S')
{
dns[px].rem(i, v[i].y / 2, 0);
}
else if(v[i].dir == 'E')
{
dve[py].rem(i, v[i].x / 2, 0);
}
else if(v[i].dir == 'W')
{
dve[py].rem(i, v[i].x / 2, 1);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
#ifdef home
freopen("nr.in","r",stdin);
freopen("nr.out","w",stdout);
#endif // home
cin>>n;
for(int i=1; i<=n; i++)
{
cin>>v[i].x>>v[i].y>>v[i].dir;
d0.push_back(v[i].x - v[i].y);
d1.push_back(v[i].x + v[i].y);
dx.push_back(v[i].x);
dy.push_back(v[i].y);
}
sort(d0.begin(),d0.end());
sort(d1.begin(),d1.end());
sort(dx.begin(),dx.end());
sort(dy.begin(),dy.end());
for(int i=1; i<=n; i++)
{
Add(i);
}
for(int i=1;i<=n;i++)
{
Build(i);
}
while(!h.empty())
{
++cnt;
while(!h.empty() && (sel[h.top().second.first] || sel[h.top().second.second]))
{
h.pop();
}
if(h.empty())
{
break;
}
int val = h.top().first;
while(!h.empty() && h.top().first == val)
{
if(!sel[h.top().second.first] && !sel[h.top().second.second])
{
Remove(h.top().second.first);
Remove(h.top().second.second);
}
else if(!sel[h.top().second.first] && sel[h.top().second.second] == cnt)
{
Remove(h.top().second.first);
}
else if(sel[h.top().second.first] == cnt && !sel[h.top().second.second])
{
Remove(h.top().second.second);
}
h.pop();
}
}
for(int i=1;i<=n;i++)
{
if(!sel[i])
{
cout<<i<<'\n';
}
}
return 0;
}
