#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<ll>
#define vvi vector<vector<ll>>
#define vs vector<string>
#define vc vector<char>
#define vb vector<bool>
#define vp vector<pair<ll, ll>>
#define vpp vector<pair<ll, pair<ll, ll>>>
#define pp pair<ll, ll>
#define qi queue<ll>
#define qp queue<pp>
#define pqi priority_queue<ll>
#define pqp priority_queue<pp>
#define mi map<ll, ll>
#define mpi map<pp, ll>
#define mip map<ll, pp>
#define mp map<pp, pp>
#define mb map<ll, bool>
#define si set<ll>
#define sp set<pp>
#define sc set<char>
#define mod 1000000007
#define inf INT_MAX
#define all(x) (x).begin(), (x).end()
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
ll n;
cin >> n;
vp a(n);
vc type(n);
vector<pair<pp, ll>> north, south, east, west;
map<ll, vp> diagES;
map<ll, vp> diagWN;
map<ll, vp> diagEN;
map<ll, vp> diagWS;
map<ll, vp> vert;
map<ll, vp> hor;
for(int i = 0; i < n; i++) {
cin >> a[i].first >> a[i].second >> type[i];
if(type[i] == 'N') {
north.push_back({a[i], i});
}
else if(type[i] == 'S') {
south.push_back({a[i], i});
}
else if(type[i] == 'W') {
west.push_back({a[i], i});
}
else {
east.push_back({a[i], i});
}
auto[x, y] = a[i];
ll d = x + y;
if(type[i] == 'E' || type[i] == 'S') {
diagES[d].push_back({y, i});
}
else {
diagWN[d].push_back({y, i});
}
d = x - y;
if(type[i] == 'E' || type[i] == 'N') {
diagEN[d].push_back({y, i});
}
else {
diagWS[d].push_back({y, i});
}
if(type[i] == 'W' || type[i] == 'E') {
hor[y].push_back({x, i});
}
else {
vert[x].push_back({y, i});
}
}
vector<int> time_of_death(n, inf);
priority_queue<pair<pair<ll, pair<string, ll>>, pp>> q;
si usedES;
for(auto&[d, v] : diagES) {
sort(all(v));
for(int i = 0; i < v.size(); i++) usedES.insert(i);
for(int i = 0; i < v.size() - 1; i++) {
ll ind1 = v[i].second, ind2 = v[i + 1].second;
if(type[ind1] == 'S' && type[ind2] == 'E') {
ll time = (abs(a[ind1].first - a[ind2].first) + abs(a[ind1].second - a[ind2].second)) / 2;
q.push({{-time, {"ES", d}}, {i, i + 1}});
}
}
}
si usedWN;
for(auto&[d, v] : diagWN) {
sort(all(v));
for(int i = 0; i < v.size(); i++) usedWN.insert(i);
for(int i = 0; i < v.size() - 1; i++) {
ll ind1 = v[i].second, ind2 = v[i + 1].second;
if(type[ind1] == 'W' && type[ind2] == 'N') {
ll time = (abs(a[ind1].first - a[ind2].first) + abs(a[ind1].second - a[ind2].second)) / 2;
q.push({{-time, {"WN", d}}, {i, i + 1}});
}
}
}
si usedEN;
for(auto&[d, v] : diagEN) {
sort(all(v));
for(int i = 0; i < v.size(); i++) usedEN.insert(i);
for(int i = 0; i < v.size() - 1; i++) {
ll ind1 = v[i].second, ind2 = v[i + 1].second;
if(type[ind1] == 'E' && type[ind2] == 'N') {
ll time = (abs(a[ind1].first - a[ind2].first) + abs(a[ind1].second - a[ind2].second)) / 2;
q.push({{-time, {"EN", d}}, {i, i + 1}});
}
}
}
si usedWS;
for(auto&[d, v] : diagWS) {
sort(all(v));
for(int i = 0; i < v.size(); i++) usedWS.insert(i);
for(int i = 0; i < v.size() - 1; i++) {
ll ind1 = v[i].second, ind2 = v[i + 1].second;
if(type[ind1] == 'S' && type[ind2] == 'W') {
ll time = (abs(a[ind1].first - a[ind2].first) + abs(a[ind1].second - a[ind2].second)) / 2;
q.push({{-time, {"WS", d}}, {i, i + 1}});
}
}
}
si usedvert;
for(auto&[d, v] : vert) {
sort(all(v));
for(int i = 0; i < v.size(); i++) usedvert.insert(i);
for(int i = 0; i < v.size() - 1; i++) {
ll ind1 = v[i].second, ind2 = v[i + 1].second;
if(type[ind1] == 'S' && type[ind2] == 'N') {
ll time = (abs(a[ind1].first - a[ind2].first) + abs(a[ind1].second - a[ind2].second)) / 2;
q.push({{-time, {"vert", d}}, {i, i + 1}});
}
}
}
si usedhor;
for(auto&[d, v] : hor) {
sort(all(v));
for(int i = 0; i < v.size(); i++) usedhor.insert(i);
for(int i = 0; i < v.size() - 1; i++) {
ll ind1 = v[i].second, ind2 = v[i + 1].second;
if(type[ind1] == 'E' && type[ind2] == 'W') {
ll time = (abs(a[ind1].first - a[ind2].first) + abs(a[ind1].second - a[ind2].second)) / 2;
q.push({{-time, {"hor", d}}, {i, i + 1}});
}
}
}
while(q.size()) {
ll curTime = -q.top().first.first;
auto[from, d] = q.top().first.second;
auto[i, j] = q.top().second;
q.pop();
vp *temp;
si *usedTemp;
if(from == "ES") {
temp = &diagES[d];
usedTemp = &usedES;
}
else if(from == "WN") {
temp = &diagWN[d];
usedTemp = &usedWN;
}
else if(from == "EN") {
temp = &diagEN[d];
usedTemp = &usedEN;
}
else if(from == "WS") {
temp = &diagWS[d];
usedTemp = &usedWS;
}
else if(from == "vert") {
temp = &vert[d];
usedTemp = &usedvert;
}
else if(from == "hor") {
temp = &hor[d];
usedTemp = &usedhor;
}
vp &v = *temp;
si &used = *usedTemp;
ll realInd1 = v[i].second;
ll realInd2 = v[j].second;
if(time_of_death[realInd1] >= curTime && time_of_death[realInd2] >= curTime) {
time_of_death[realInd1] = curTime;
time_of_death[realInd2] = curTime;
}
if((time_of_death[realInd1] >= curTime && time_of_death[realInd2] >= curTime) ||
(time_of_death[realInd1] < curTime && time_of_death[realInd2] < curTime)) {
auto it1 = used.lower_bound(i);
auto it2 = used.upper_bound(j);
if(it1 == used.begin() || it2 == used.end()) {
used.erase(i);
used.erase(j);
continue;
}
it1--;
ll newI = *it1, newJ = *it2;
ll ind1 = v[newI].second, ind2 = v[newJ].second;
ll time = (abs(a[ind1].first - a[ind2].first) + abs(a[ind1].second - a[ind2].second)) / 2;
q.push({{-time, {from, d}}, {newI, newJ}});
used.erase(i);
used.erase(j);
}
else if(time_of_death[realInd1] < curTime) {
auto it1 = used.lower_bound(i);
if(it1 == used.begin()) {
used.erase(i);
used.erase(j);
continue;
}
it1--;
ll newI = *it1, newJ = j;
ll ind1 = v[newI].second, ind2 = v[newJ].second;
ll time = (abs(a[ind1].first - a[ind2].first) + abs(a[ind1].second - a[ind2].second)) / 2;
q.push({{-time, {from, d}}, {newI, newJ}});
used.erase(i);
}
else if(time_of_death[realInd2] < curTime) {
auto it2 = used.upper_bound(j);
if(it2 == used.end()) {
used.erase(i);
used.erase(j);
continue;
}
ll newI = i, newJ = *it2;
ll ind1 = v[newI].second, ind2 = v[newJ].second;
ll time = (abs(a[ind1].first - a[ind2].first) + abs(a[ind1].second - a[ind2].second)) / 2;
q.push({{-time, {from, d}}, {newI, newJ}});
used.erase(j);
}
}
for(int i = 0; i < n; i++) {
if(time_of_death[i] == inf) cout << i + 1 << '\n';
}
return 0;
}
/*
3
4 0 S
2 2 E
0 4 E
3
5
2 2 E
4 0 S
0 4 E
1 3 S
3 1 S
2
4
0 6 E
2 4 E
4 2 S
6 0 S
2
0 0 E
2 2 N
4
0 0 S
0 2 E
2 2 W
4 4 W
*/
