#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define fi first
#define se second
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int rand(int l,int r){return uniform_int_distribution<int>(l, r)(rng);}
inline ll rand(ll l,ll r){return uniform_int_distribution<ll>(l, r)(rng64);}
#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
struct pair_hash{
size_t operator()(const pair<int,int>&x)const{
return hash<long long>()(((long long)x.first)^(((long long)x.second)<<32));
}
};
const int MAXN = 2e5 + 7;
int X[MAXN];
int Y[MAXN];
char type[MAXN];
int deleted[MAXN];
map<int, set<pii>> row;
map<int, set<pii>> column;
//pierwsza przekątna -> x + y
map<int, set<pii>> firstDiagonalUp;
map<int, set<pii>> firstDiagonalDown;
//druga przekątna -> x - y
map<int, set<pii>> secondDiagonalUp;
map<int, set<pii>> secondDiagonalDown;
int n;
priority_queue<pair<int, pii>> pq;
void init(){
for(auto&[xddd, curr] : row){
auto it = curr.begin();
while(it != curr.end()){
if(type[(*it).se] == 'W'){
it++;
continue;
}
auto it2 = it;
it2++;
if(it2 == curr.end()){
break;
}
if(type[(*it2).se] == 'E'){
it = it2;
continue;
}
pq.push(mp(-abs((*it).fi - (*it2).fi) / 2, mp((*it).se, (*it2).se)));
it = it2;
it2++;
}
}
for(auto&[xddd, curr] : column){
auto it = curr.begin();
while(it != curr.end()){
if(type[(*it).se] == 'N'){
it++;
continue;
}
auto it2 = it;
it2++;
if(it2 == curr.end()){
break;
}
if(type[(*it2).se] == 'S'){
it = it2;
continue;
}
pq.push(mp(-abs((*it).fi - (*it2).fi) / 2, mp((*it).se, (*it2).se)));
it = it2;
it2++;
}
}
for(auto&[xddd, curr] : firstDiagonalUp){
auto it = curr.begin();
while(it != curr.end()){
if(type[(*it).se] == 'W'){
it++;
continue;
}
auto it2 = it;
it2++;
if(it2 == curr.end()){
break;
}
if(type[(*it2).se] == 'N'){
it = it2;
continue;
}
pq.push(mp(-abs((*it).fi - (*it2).fi), mp((*it).se, (*it2).se)));
it = it2;
it2++;
}
}
for(auto&[xddd, curr] : firstDiagonalDown){
auto it = curr.begin();
while(it != curr.end()){
if(type[(*it).se] == 'S'){
it++;
continue;
}
auto it2 = it;
it2++;
if(it2 == curr.end()){
break;
}
if(type[(*it2).se] == 'E'){
it = it2;
continue;
}
pq.push(mp(-abs((*it).fi - (*it2).fi), mp((*it).se, (*it2).se)));
it = it2;
it2++;
}
}
for(auto&[xddd, curr] : secondDiagonalUp){
auto it = curr.begin();
while(it != curr.end()){
if(type[(*it).se] == 'N'){
it++;
continue;
}
auto it2 = it;
it2++;
if(it2 == curr.end()){
break;
}
if(type[(*it2).se] == 'E'){
it = it2;
continue;
}
pq.push(mp(-abs((*it).fi - (*it2).fi), mp((*it).se, (*it2).se)));
it = it2;
it2++;
}
}
for(auto&[xddd, curr] : secondDiagonalDown){
auto it = curr.begin();
while(it != curr.end()){
if(type[(*it).se] == 'W'){
it++;
continue;
}
auto it2 = it;
it2++;
if(it2 == curr.end()){
break;
}
if(type[(*it2).se] == 'S'){
it = it2;
continue;
}
pq.push(mp(-abs((*it).fi - (*it2).fi), mp((*it).se, (*it2).se)));
it = it2;
it2++;
}
}
}
//pierwsze jest a, drugie jest b
void del(int a, int b, int w, set<pii>& curr, int flag = 0){
// cerr << a << ' ' << b << ' ' << w << ' ' << flag << '\n';
// cerr << sz(curr) << '\n';
// for(auto ele : curr){
// cerr << ele << ' ' << type[ele.se] << '\n';
// }
// cerr << '\n';
auto it = curr.find(mp((flag ? Y[a] : X[a]), a));
auto it2 = curr.find(mp((flag ? Y[b] : X[b]), b));
++it2;
if(it != curr.begin() && it2 != curr.end()){
--it;
// cerr << (*it) << ' ' << (*it2) << '\n';
if(type[(*it).se] == type[a] && type[(*it2).se] == type[b]){
pq.push(mp(-abs((*it).fi - (*it2).fi) / w, mp((*it).se, (*it2).se)));
}
}
curr.erase(mp((flag ? Y[a] : X[a]), a));
curr.erase(mp((flag ? Y[b] : X[b]), b));
}
void deleteInfo(int a, int b){
// cerr << "DELETING: " << a << ' ' << b << '\n';
// cerr << type[a] << ' ' << type[b] << '\n';
if(type[a] == 'N'){
if(type[b] == 'W'){
del(a, b, 1, firstDiagonalUp[X[a] + Y[a]]);
return;
}else if(type[b] == 'E'){
del(b, a, 1, secondDiagonalUp[X[a] - Y[a]]);
return;
}else if(type[b] == 'S'){
del(b, a, 2, column[X[a]], 1);
return;
}
}else if(type[a] == 'W'){
if(type[b] == 'E'){
del(b, a, 2, row[Y[a]]);
return;
}else if(type[b] == 'S'){
del(b, a, 1, secondDiagonalDown[X[a] - Y[a]]);
return;
}
}else if(type[a] == 'E' && type[b] == 'S'){
del(a, b, 1, firstDiagonalDown[X[a] + Y[a]]);
return;
}
swap(a, b);
deleteInfo(a, b);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
for(int i = 1; i <= n; i++){
cin >> X[i] >> Y[i] >> type[i];
if(type[i] == 'S' || type[i] == 'N'){
column[X[i]].insert(mp(Y[i], i));
}else{
row[Y[i]].insert(mp(X[i], i));
}
if(type[i] == 'N'){
firstDiagonalUp[X[i] + Y[i]].insert(mp(X[i], i));
secondDiagonalUp[X[i] - Y[i]].insert(mp(X[i], i));
}else if(type[i] == 'S'){
firstDiagonalDown[X[i] + Y[i]].insert(mp(X[i], i));
secondDiagonalDown[X[i] - Y[i]].insert(mp(X[i], i));
}else if(type[i] == 'W'){
firstDiagonalUp[X[i] + Y[i]].insert(mp(X[i], i));
secondDiagonalDown[X[i] - Y[i]].insert(mp(X[i], i));
}else{
firstDiagonalDown[X[i] + Y[i]].insert(mp(X[i], i));
secondDiagonalUp[X[i] - Y[i]].insert(mp(X[i], i));
}
}
init();
while(sz(pq)){
pair<int, pii> curr = pq.top();
pq.pop();
int a = curr.se.fi;
int b = curr.se.se;
//cerr << curr.fi << ' ' << a << ' ' << b << '\n';
deleteInfo(a, b);
if(a == b || (deleted[a] && deleted[b])){
continue;
}
if(deleted[a]){
if(curr.fi == deleted[a]){
deleted[b] = curr.fi;
}
}else if(deleted[b]){
if(curr.fi == deleted[b]){
deleted[a] = curr.fi;
}
}else{
deleted[a] = curr.fi;
deleted[b] = curr.fi;
}
// cerr << "===\n";
}
// cerr << "ANS:\n";
for(int i = 1; i <= n; i++){
if(deleted[i] == 0){
cout << i << '\n';
}
}
return 0;
}
