#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 200005;
int n;
int x[N], y[N];
char ty[N];
int f(const pair<int, int>& t1, const pair<int, int>& t2)
{
return (abs(t1.fi - t2.fi) + abs(t1.se - t2.se)) / 2;
}
set<pair<int, pair<pair<int, int>, pair<int, int> > > > orz;
void ave(set<pair<pair<int, int>, bool> >& s, int x, int y, bool z, int ttt)
{
if (ttt == +1)
{
if (!s.empty())
{
auto it = s.lower_bound(m_p(m_p(x, y), z));
if (it != s.end() && it != s.begin())
{
if (it->se == true)
{
pair<int, int> r = it->fi;
--it;
if (it->se == false)
{
pair<int, int> l = it->fi;
orz.erase(m_p(f(l, r), m_p(l, r)));
}
}
}
}
s.insert(m_p(m_p(x, y), z));
auto it = s.find(m_p(m_p(x, y), z));
if (z == false)
{
pair<int, int> l = m_p(x, y);
++it;
if (it != s.end())
{
if (it->se == true)
{
pair<int, int> r = it->fi;
orz.insert(m_p(f(l, r), m_p(l, r)));
}
}
}
else
{
pair<int, int> r = m_p(x, y);
if (it != s.begin())
{
--it;
if (it->se == false)
{
pair<int, int> l = it->fi;
orz.insert(m_p(f(l, r), m_p(l, r)));
}
}
}
}
else if (ttt == -1)
{
auto it = s.find(m_p(m_p(x, y), z));
if (z == false)
{
pair<int, int> l = m_p(x, y);
++it;
if (it != s.end())
{
if (it->se == true)
{
pair<int, int> r = it->fi;
orz.erase(m_p(f(l, r), m_p(l, r)));
}
}
}
else
{
pair<int, int> r = m_p(x, y);
if (it != s.begin())
{
--it;
if (it->se == false)
{
pair<int, int> l = it->fi;
orz.erase(m_p(f(l, r), m_p(l, r)));
}
}
}
s.erase(m_p(m_p(x, y), z));
if (!s.empty())
{
auto it = s.lower_bound(m_p(m_p(x, y), z));
if (it != s.end() && it != s.begin())
{
if (it->se == true)
{
pair<int, int> r = it->fi;
--it;
if (it->se == false)
{
pair<int, int> l = it->fi;
orz.insert(m_p(f(l, r), m_p(l, r)));
}
}
}
}
}
else
assert(false);
}
vector<int> s, d, xx, yy;
set<pair<pair<int, int>, bool> > ew[N], sn[N], es[N], nw[N], en[N], sw[N];
void ave(int x, int y, char ty, int ttt)
{
// EW
if (ty == 'E')
{
int i = lower_bound(all(yy), y) - yy.begin();
ave(ew[i], x, y, false, ttt);
}
if (ty == 'W')
{
int i = lower_bound(all(yy), y) - yy.begin();
ave(ew[i], x, y, true, ttt);
}
// SN
if (ty == 'S')
{
int i = lower_bound(all(xx), x) - xx.begin();
ave(sn[i], x, y, false, ttt);
}
if (ty == 'N')
{
int i = lower_bound(all(xx), x) - xx.begin();
ave(sn[i], x, y, true, ttt);
}
// ES
if (ty == 'E')
{
int i = lower_bound(all(s), x + y) - s.begin();
ave(es[i], x, y, false, ttt);
}
if (ty == 'S')
{
int i = lower_bound(all(s), x + y) - s.begin();
ave(es[i], x, y, true, ttt);
}
// NW
if (ty == 'N')
{
int i = lower_bound(all(s), x + y) - s.begin();
ave(nw[i], x, y, false, ttt);
}
if (ty == 'W')
{
int i = lower_bound(all(s), x + y) - s.begin();
ave(nw[i], x, y, true, ttt);
}
// EN
if (ty == 'E')
{
int i = lower_bound(all(d), x - y) - d.begin();
ave(en[i], x, y, false, ttt);
}
if (ty == 'N')
{
int i = lower_bound(all(d), x - y) - d.begin();
ave(en[i], x, y, true, ttt);
}
// SW
if (ty == 'S')
{
int i = lower_bound(all(d), x - y) - d.begin();
ave(sw[i], x, y, false, ttt);
}
if (ty == 'W')
{
int i = lower_bound(all(d), x - y) - d.begin();
ave(sw[i], x, y, true, ttt);
}
}
bool c[N];
void solv()
{
cin >> n;
map<pair<int, int>, int> mp;
for (int i = 1; i <= n; ++i)
{
cin >> x[i] >> y[i] >> ty[i];
mp[m_p(x[i], y[i])] = i;
}
for (int i = 1; i <= n; ++i)
{
s.push_back(x[i] + y[i]);
d.push_back(x[i] - y[i]);
xx.push_back(x[i]);
yy.push_back(y[i]);
}
sort(all(s));
sort(all(d));
sort(all(xx));
sort(all(yy));
for (int i = 1; i <= n; ++i)
{
ave(x[i], y[i], ty[i], 1);
}
while (!orz.empty())
{
int d = orz.begin()->fi;
vector<int> t;
while (!orz.empty())
{
auto it = orz.begin();
if (it->fi != d)
break;
int i = mp[it->se.fi];
int j = mp[it->se.se];
if (c[i] || c[j])
{
orz.erase(it);
continue;
}
t.push_back(i);
t.push_back(j);
orz.erase(it);
}
for (int i = 0; i < sz(t); ++i)
{
if (c[t[i]])
continue;
c[t[i]] = true;
ave(x[t[i]], y[t[i]], ty[t[i]], -1);
}
}
for (int i = 1; i <= n; ++i)
{
if (!c[i])
cout << i << "\n";
}
}
int main()
{
#ifdef SOMETHING
freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#endif // SOMETHING
ios_base::sync_with_stdio(false), cin.tie(0);
int tt = 1;
//cin >> tt;
while (tt--)
{
solv();
}
return 0;
}
