#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;
const char nl = '\n';
void fastIO() {
ios::sync_with_stdio(false);
cin.tie(0);
}
map<char, int> conv = {{'S', 0}, {'N', 1}, {'E', 2}, {'W', 3}};
int N;
ll norm(ll x, ll y) {
x %= y;
x += y;
x %= y;
return x;
}
ll intersect(pair<int, ii> s1, pair<int, ii> s2) {
// cout<<"at "<<"("<<s1.fi<<", "<<s1.se.fi<<", "<<s1.se.se<<"); ("<<s2.fi<<", "<<s2.se.fi<<", "<<s2.se.se<<")"<<endl;
// time if intersect, -1 if not
if (s1.fi > s2.fi) // ensure first is less than second
swap(s1, s2);
if (s1.fi == s2.fi) // if same direction, never intersect
return -1;
if (s1.fi == 0 && s2.fi == 1) { // x coord const, first increasing
if (s1.se.fi != s2.se.fi)
return -1;
if (norm(s1.se.se + s2.se.se) == 1 || s1.se.se > s2.se.se)
return -1;
return abs(s2.se.se - s1.se.se) / 2;
}
if (s1.fi == 2 && s2.fi == 3) { // y coord const, first increasing
if (s1.se.se != s2.se.se)
return -1;
if (norm(s1.se.fi + s2.se.fi) == 1 || s1.se.fi > s2.se.fi)
return -1;
return abs(s2.se.fi - s1.se.fi) / 2;
}
// first going N/S, other going E/W
ii ins = {s1.se.fi, s2.se.se};
// cout<<"ins: "<<ins.fi<<", "<<ins.se<<endl;
ll t1 = ins.se - s1.se.se;
if (s1.fi == 1)
t1 = -t1;
ll t2 = ins.fi - s2.se.fi;
// cout<<"t1, t2: "<<t1<<" "<<t2<<endl;
if (s2.fi == 3)
t2 = -t2;
if (t1 == t2 && t1 > 0)
return t1;
return -1;
}
vector<pair<ll, ii>> findDiag(map<ll, vector<pair<ii, ii>>> alld) {
// set of {{x, y}, {type, id}}
vector<pair<ll, ii>> badpairs;
// {dist, {id1, id2}}
for (pair<ll, vector<pair<ii, ii>>> pr : alld) {
// cout<<"at "<<pr.fi<<endl;
sort(pr.se.begin(), pr.se.end());
int K = pr.se.size();
vi posX;
vector<char> dir; // A = east, B = south
vi idx;
for (int j = 0; j < K; j++) {
posX.pb(pr.se[j].fi.fi);
if (pr.se[j].se.fi == 2)
dir.pb('A');
else
dir.pb('B');
idx.pb(pr.se[j].se.se);
}
/* cout<<"K: "<<K<<endl;
cout<<"dir: ";
for (char c : dir)
cout<<c<<" ";
cout<<endl;
cout<<"idx: ";
for (int x : idx)
cout<<x<<" ";
cout<<endl;*/
// remove all consec
stack<ii> q; // all existing A ids, most recent on top
// {id, pos}
for (int j = 0; j < K; j++) {
if (dir[j] == 'A') {
q.push({idx[j], j});
}
else {
if (!q.empty()) {
ii x = q.top();
q.pop();
// cout<<"removed "<<x<<" "<<idx[j]<<endl;
badpairs.pb({abs(posX[x.se] - posX[j]), {x.fi, idx[j]}});
}
}
}
}
return badpairs;
}
vector<pair<ll, ii>> findLine(map<ll, vector<pair<ll, ii>>> alld) {
// set of {x, {type, id}}
vector<pair<ll, ii>> badpairs;
// {dist, {id1, id2}}
for (pair<ll, vector<pair<ll, ii>>> pr : alld) {
// cout<<"at "<<pr.fi<<endl;
sort(pr.se.begin(), pr.se.end());
int K = pr.se.size();
vi posX;
vector<char> dir; // A = increasing, B = decreasing
vi idx;
for (int j = 0; j < K; j++) {
posX.pb(pr.se[j].fi);
if (pr.se[j].se.fi == 0)
dir.pb('A');
else
dir.pb('B');
idx.pb(pr.se[j].se.se);
}
/* cout<<"K: "<<K<<endl;
cout<<"dir: ";
for (char c : dir)
cout<<c<<" ";
cout<<endl;
cout<<"idx: ";
for (int x : idx)
cout<<x<<" ";
cout<<endl;*/
// remove all consec
stack<ii> q; // all existing A ids, most recent on top
// {id, pos}
for (int j = 0; j < K; j++) {
if (dir[j] == 'A') {
q.push({idx[j], j});
}
else {
if (!q.empty()) {
ii x = q.top();
q.pop();
// cout<<"removed "<<x<<" "<<idx[j]<<endl;
badpairs.pb({abs(posX[x.se] - posX[j]) / 2, {x.fi, idx[j]}});
}
}
}
}
return badpairs;
}
int main() {
fastIO();
cin>>N;
vector<pair<int, ii>> ships;
// {type, {x, y}}
map<ll, vector<pair<ii, ii>>> alldSE; // all on diagonal x+y=i, going down
// set of {{x, y}, {type, id}}
map<ll, vector<pair<ii, ii>>> alldSW;
map<ll, vector<pair<ii, ii>>> alldNE;
map<ll, vector<pair<ii, ii>>> alldNW;
map<ll, vector<pair<ll, ii>>> alldNS0; // even y pos
map<ll, vector<pair<ll, ii>>> alldNS1; // odd y pos
// all on same x value, set of {y, {type, id}}
map<ll, vector<pair<ll, ii>>> alldEW0;
map<ll, vector<pair<ll, ii>>> alldEW1;
for (int i = 0; i < N; i++) {
ll x, y; char d;
cin>>x>>y>>d;
ships.pb({conv[d], {x, y}});
if (conv[d] == 0) { // south
alldSE[x + y].pb({{x, y}, {0, i}});
alldSW[-x + y].pb({{-x, y}, {0, i}});
}
if (conv[d] == 2) { // east
alldSE[x + y].pb({{x, y}, {2, i}});
alldNE[x - y].pb({{x, -y}, {2, i}});
}
if (conv[d] == 1) { // north
alldNE[x - y].pb({{x, -y}, {0, i}});
alldNW[-x - y].pb({{-x, -y}, {0, i}});
}
if (conv[d] == 3) { // west
alldSW[-x + y].pb({{-x, y}, {2, i}});
alldNW[-x - y].pb({{-x, -y}, {2, i}});
}
if (conv[d] == 0 || conv[d] == 1) { // S or N
if (y % 2 == 0)
alldNS0[x].pb({y, {conv[d], i}});
else
alldNS1[x].pb({y, {conv[d], i}});
}
if (conv[d] == 2 || conv[d] == 3) { // E or W
if (x % 2 == 0)
alldEW0[y].pb({x, {conv[d] - 2, i}});
else
alldEW1[y].pb({x, {conv[d] - 2, i}});
}
}
/* cout<<"ships: ";
for (pair<int, ii> p : ships)
cout<<"("<<p.fi<<", "<<p.se.fi<<", "<<p.se.se<<"); ";
cout<<endl;*/
vector<vector<pair<ll, ii>>> allv = {findDiag(alldSE), findDiag(alldSW), findDiag(alldNE), findDiag(alldNW), findLine(alldNS0), findLine(alldNS1), findLine(alldEW0), findLine(alldEW1)};
// then sort all the distances created
/* for (vector<pair<ll, ii>> v : allv) {
for (pair<ll, ii> p : v)
cout<<"("<<p.fi<<", "<<p.se.fi<<", "<<p.se.se<<"); ";
cout<<endl;
}*/
vector<pair<ll, ii>> sink;
for (vector<pair<ll, ii>> v : allv) {
for (pair<ll, ii> p : v)
sink.pb(p);
}
/* cout<<"sinking: "<<endl;
for (pair<ll, ii> p : sink)
cout<<p.fi<<" "<<p.se.fi<<" "<<p.se.se<<endl;*/
map<ll, vector<ii>> allr;
for (pair<ll, ii> p : sink) {
allr[p.fi].pb(p.se);
}
vector<bool> alive(N, true); // still alive
for (pair<ll, vector<ii>> pr : allr) {
// cout<<"at "<<pr.fi<<endl;
set<int> toremove;
for (ii p : pr.se) {
if (alive[p.fi] && alive[p.se]) {
toremove.insert(p.fi);
toremove.insert(p.se);
}
}
for (int x : toremove) {
// cout<<"removed "<<x<<endl;
alive[x] = false;
}
}
// cout<<"ANSWER: "<<endl;
for (int i = 0; i < N; i++) {
if (alive[i])
cout<<(i + 1)<<endl;
}
}
