// -------------------- Includes -------------------- //
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <stdio.h>
#include <cstdlib>
#include <stdlib.h>
#include <array>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <math.h>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <list>
#include <iterator>
#include <numeric>
#include <complex>
#include <tuple>
#include <utility>
#include <cassert>
#include <assert.h>
#include <climits>
#include <limits.h>
#include <ctime>
#include <time.h>
#include <random>
#include <chrono>
#include <fstream>
using namespace std;
// -------------------- Typedefs -------------------- //
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
// -------------------- Defines -------------------- //
#define pr pair
#define mpr make_pair
#define ff first
#define ss second
#define mset multiset
#define mmap multimap
#define uset unordered_set
#define umap unordered_map
#define umset unordered_multiset
#define ummap unordered_multimap
#define pqueue priority_queue
#define sz(x) (int((x).size()))
#define len(x) (int((x).length()))
#define all(x) (x).begin(), (x).end()
#define clr(x) (x).clear()
#define ft front
#define bk back
#define pf push_front
#define pb push_back
#define popf pop_front
#define popb pop_back
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
// -------------------- Constants -------------------- //
const int MAX = int(1e9 + 5);
const ll MAXL = ll(1e18 + 5);
const ll MOD = ll(1e9 + 7);
const ll MOD2 = ll(998244353);
// -------------------- Functions -------------------- //
void fastio()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
return;
}
void precision(int x)
{
cout << fixed << setprecision(x);
return;
}
ll gcd0(ll a, ll b)
{
while (b) {
a %= b;
swap(a, b);
}
return a;
}
ll lcm0(ll a, ll b)
{
return a / gcd0(a, b) * b;
}
bool is_prime(ll a)
{
if (a == 1) return false;
for (ll i = 2; i * i <= a; i++) if (a % i == 0) return false;
return true;
}
bool is_square(ll a)
{
ll b = ll(sqrtl(ld(a)));
return (b * b == a);
}
bool is_cube(ll a)
{
ll b = ll(cbrtl(ld(a)));
return (b * b * b == a);
}
int digit_sum(ll a)
{
int sum = 0;
while (a) {
sum += int(a % 10);
a /= 10;
}
return sum;
}
ll binpow(ll a, int b)
{
ll ans = 1;
while (b) {
if (b & 1) ans *= a;
b >>= 1;
a *= a;
}
return ans;
}
ll binpow_mod(ll a, ll b, ll mod)
{
ll ans = 1;
while (b) {
if (b & 1) ans = (ans * a) % mod;
b >>= 1;
a = (a * a) % mod;
}
return ans;
}
ll factorial(int a)
{
ll ans = 1;
for (int i = 2; i <= a; i++) ans *= ll(i);
return ans;
}
ll factorial_mod(int a, ll mod)
{
ll ans = 1;
for (int i = 2; i <= a; i++) ans = (ans * ll(i)) % mod;
return ans;
}
// -------------------- Solution -------------------- //
const pr<int, pr<int, int>> null = mpr(-1, mpr(-1, -1));
struct ship
{
int x, y;
char d;
vector<int> vo;
};
const int N = 200005;
ship a[N];
bool used[N];
int n;
vector<pr<pr<int, pr<int, int>>, pr<int, int>>> v;
vector<pr<int, int>> vv;
pr<int, pr<int, int>> col(ship x, ship y)
{
if (x.d == y.d) return null;
if (x.x == y.x) {
if (x.d == 'E' || x.d == 'W' || y.d == 'E' || y.d == 'W') return null;
if (x.y > y.y) swap(x, y);
if (x.d == 'S' && y.d == 'N') return mpr((y.y - x.y) / 2, mpr(x.x, (x.y + y.y) / 2));
return null;
}
if (x.y == y.y) {
if (x.d == 'N' || x.d == 'S' || y.d == 'N' || y.d == 'S') return null;
if (x.x > y.x) swap(x, y);
if (x.d == 'E' && y.d == 'W') return mpr((y.x - x.x) / 2, mpr((x.x + y.x) / 2, x.y));
return null;
}
if (x.x - x.y == y.x - y.y) {
if (x.x > y.x) swap(x, y);
if (x.d == 'E' && y.d == 'N') return mpr(y.x - x.x, mpr(y.x, x.y));
if (x.d == 'S' && y.d == 'W') return mpr(y.x - x.x, mpr(x.x, y.y));
return null;
}
if (x.x + x.y == y.x + y.y) {
if (x.x > y.x) swap(x, y);
if (x.d == 'N' && y.d == 'W') return mpr(y.x - x.x, mpr(x.x, y.y));
if (x.d == 'E' && y.d == 'S') return mpr(y.x - x.x, mpr(y.x, x.y));
return null;
}
return null;
}
map<int, vector<pr<int, int>>> mpx, mpy, mp11, mp12, mp21, mp22;
void init()
{
int i, j;
for (i = 1; i <= n; i++) {
if (a[i].d == 'N') {
mpx[a[i].x].pb(mpr(a[i].y, i));
mp11[a[i].x - a[i].y].pb(mpr(a[i].x, i));
mp21[a[i].x + a[i].y].pb(mpr(a[i].x, i));
}
else if (a[i].d == 'S') {
mpx[a[i].x].pb(mpr(a[i].y, i));
mp12[a[i].x - a[i].y].pb(mpr(a[i].x, i));
mp22[a[i].x + a[i].y].pb(mpr(a[i].x, i));
}
else if (a[i].d == 'E') {
mpy[a[i].y].pb(mpr(a[i].x, i));
mp11[a[i].x - a[i].y].pb(mpr(a[i].x, i));
mp22[a[i].x + a[i].y].pb(mpr(a[i].x, i));
}
else {
mpy[a[i].y].pb(mpr(a[i].x, i));
mp12[a[i].x - a[i].y].pb(mpr(a[i].x, i));
mp21[a[i].x + a[i].y].pb(mpr(a[i].x, i));
}
}
return;
}
set<pr<pr<int, pr<int, int>>, pr<int, int>>> st;
void solve()
{
int i, j;
cin >> n;
for (i = 1; i <= n; i++) cin >> a[i].x >> a[i].y >> a[i].d;
init();
for (auto p : mpx) sort(all(mpx[p.ff]));
for (auto p : mpy) sort(all(mpy[p.ff]));
for (auto p : mp11) sort(all(mp11[p.ff]));
for (auto p : mp12) sort(all(mp12[p.ff]));
for (auto p : mp21) sort(all(mp21[p.ff]));
for (auto p : mp22) sort(all(mp22[p.ff]));
stack<int> st;
for (auto p : mpx) {
while (!st.empty()) st.pop();
for (i = 0; i < sz(p.ss); i++) {
if (a[p.ss[i].ss].d == 'N' && !st.empty() && a[st.top()].d == 'S') {
a[p.ss[i].ss].vo.pb(st.top());
a[st.top()].vo.pb(p.ss[i].ss);
st.pop();
}
else st.push(p.ss[i].ss);
}
}
for (auto p : mpy) {
while (!st.empty()) st.pop();
for (i = 0; i < sz(p.ss); i++) {
if (a[p.ss[i].ss].d == 'W' && !st.empty() && a[st.top()].d == 'E') {
a[p.ss[i].ss].vo.pb(st.top());
a[st.top()].vo.pb(p.ss[i].ss);
st.pop();
}
else st.push(p.ss[i].ss);
}
}
for (auto p : mp11) {
while (!st.empty()) st.pop();
for (i = 0; i < sz(p.ss); i++) {
if (a[p.ss[i].ss].d == 'N' && !st.empty() && a[st.top()].d == 'E') {
a[p.ss[i].ss].vo.pb(st.top());
a[st.top()].vo.pb(p.ss[i].ss);
st.pop();
}
else st.push(p.ss[i].ss);
}
}
for (auto p : mp12) {
while (!st.empty()) st.pop();
for (i = 0; i < sz(p.ss); i++) {
if (a[p.ss[i].ss].d == 'W' && !st.empty() && a[st.top()].d == 'S') {
a[p.ss[i].ss].vo.pb(st.top());
a[st.top()].vo.pb(p.ss[i].ss);
st.pop();
}
else st.push(p.ss[i].ss);
}
}
for (auto p : mp21) {
while (!st.empty()) st.pop();
for (i = 0; i < sz(p.ss); i++) {
if (a[p.ss[i].ss].d == 'W' && !st.empty() && a[st.top()].d == 'N') {
a[p.ss[i].ss].vo.pb(st.top());
a[st.top()].vo.pb(p.ss[i].ss);
st.pop();
}
else st.push(p.ss[i].ss);
}
}
for (auto p : mp22) {
while (!st.empty()) st.pop();
for (i = 0; i < sz(p.ss); i++) {
if (a[p.ss[i].ss].d == 'S' && !st.empty() && a[st.top()].d == 'E') {
a[p.ss[i].ss].vo.pb(st.top());
a[st.top()].vo.pb(p.ss[i].ss);
st.pop();
}
else st.push(p.ss[i].ss);
}
}
pr<int, pr<int, int>> e;
for (i = 1; i < n; i++) {
for (j = 0; j < sz(a[i].vo); j++) {
if (a[i].vo[j] < i) continue;
e = col(a[i], a[a[i].vo[j]]);
if (e == null) continue;
v.pb(mpr(e, mpr(i, a[i].vo[j])));
}
}
sort(all(v));
int ind = 0;
while (ind < sz(v)) {
clr(vv);
e = v[ind].ff;
vv.pb(v[ind].ss);
for (i = ind + 1; i < sz(v); i++) {
if (v[i].ff != e) break;
if (used[v[i].ss.ff] || used[v[i].ss.ss]) continue;
vv.pb(v[i].ss);
}
for (i = 0; i < sz(vv); i++) used[vv[i].ff] = used[vv[i].ss] = true;
while (i < sz(v) && (used[v[i].ss.ff] || used[v[i].ss.ss])) i++;
ind = i;
}
for (i = 1; i <= n; i++) if (!used[i]) cout << i << "\n";
return;
}
void precalc()
{
return;
}
int main()
{
fastio();
precalc();
int tests = 1, tc;
//cin >> tests;
for (tc = 1; tc <= tests; tc++) {
solve();
}
return 0;
}
/*
# # # # # # # # # # # # # # # # #
# # # # # # # # # #
# # # # # # # # # # # # #
# # # # # # # # # # # #
# # # # # # # # # # # # # #
*/
