#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define vi vector<int>
#define si set<int>
#define vb vector<bool>
#define vll vector<ll>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vvll vector<vector<ll>>
struct Ship {
int x, y, ix;
};
void solve() {
// need 3 different ways of sorting
// 0. along x + y
// 1. along x - y
// 2. along the direction of travel (y for N/S, x for E/W)
ll N;
cin >> N;
vector<vector<Ship>> S(4);
vector<pii> shipCoord(N);
vector<int> shipDir(N);
map<char, int> indMap;
indMap['N'] = 0;
indMap['W'] = 1;
indMap['S'] = 2;
indMap['E'] = 3;
priority_queue<tuple<ll, ll, ll>, vector<tuple<ll, ll, ll>>,
greater<tuple<ll, ll, ll>>>
pq;
int x, y;
char c;
for (int i = 0; i < N; i++) {
cin >> x >> y >> c;
shipCoord[i] = {x, y};
shipDir[i] = indMap[c];
S[indMap[c]].push_back({x, y, i});
}
vb active(N, true);
vector<map<int, map<int, Ship>>> mp1(4), mp2(4), mp3(4), mp4(4);
for (int i = 0; i < 4; i++) {
for (auto j : S[i]) {
int ix = j.x + (i % 2 == 0 ? 1 : -1) * j.y;
int key = (i % 2 == 0) ? j.y : j.x;
mp1[i][ix][key] = j;
}
for (auto j : S[(i + 1) % 4]) {
int ix = j.x + (i % 2 == 0 ? 1 : -1) * j.y;
int key = (i % 2 == 0) ? j.y : j.x;
mp2[i][ix][key] = j;
}
}
for (int i : {2, 3}) {
for (auto j : S[i]) {
int ix = (i == 2 ? j.x : j.y);
int rix = (i == 2 ? j.y : j.x);
mp3[i][ix][rix] = j;
}
for (auto j : S[(i + 2) % 4]) {
int ix = (i == 2 ? j.x : j.y);
int rix = (i == 2 ? j.y : j.x);
mp4[i][ix][rix] = j;
}
}
auto pushMp4 = [&](int i, map<int, map<int, Ship>>::iterator &k) {
if (k->second.empty()) {
k++;
return;
}
auto j = k->second.rbegin();
map<int, Ship>::iterator match;
if (mp4[i][k->first].size() == 0) {
k++;
return;
}
if (i == 2) {
match = mp4[i][k->first].lower_bound(j->second.y);
} else {
match = mp4[i][k->first].lower_bound(j->second.x);
}
if (match == mp4[i][k->first].end()) {
k++;
return;
}
int diff = (i == 2) ? abs(j->second.y - match->second.y) / 2
: abs(j->second.x - match->second.x) / 2;
pq.push(make_tuple(diff, j->second.ix, match->second.ix));
mp4[i][k->first].erase(match);
k++;
};
auto pushMp2 = [&](int i, map<int, map<int, Ship>>::iterator &k) {
if (k->second.empty()) {
k++;
return;
}
if (i <= 1) {
auto j = k->second.begin();
map<int, Ship>::iterator match;
if (mp2[i][k->first].size() == 0) {
k++;
return;
}
if (i == 0)
match = mp2[i][k->first].lower_bound(j->second.y);
else
match = mp2[i][k->first].lower_bound(j->second.x);
if (match == mp2[i][k->first].begin()) {
k++;
return;
}
--match;
int xdiff = abs(j->second.x - match->second.x);
pq.push(make_tuple(xdiff, j->second.ix, match->second.ix));
} else {
auto j = k->second.rbegin();
map<int, Ship>::iterator match;
if (mp2[i][k->first].size() == 0) {
k++;
return;
}
if (i == 2)
match = mp2[i][k->first].lower_bound(j->second.y);
else
match = mp2[i][k->first].lower_bound(j->second.x);
if (match == mp2[i][k->first].end()) {
k++;
return;
}
int xdiff = abs(j->second.x - match->second.x);
pq.push(make_tuple(xdiff, j->second.ix, match->second.ix));
}
k++;
};
// setup priority queue first
for (int i = 0; i < 4; i++) {
// take care of the diagonals
for (auto k = mp1[i].begin(); k != mp1[i].end();) {
pushMp2(i, k);
}
}
for (int i : {2, 3}) {
for (auto k = mp3[i].begin(); k != mp3[i].end();) {
pushMp4(i, k);
}
}
auto remDir1 = [&](int dir, int ix, vector<map<int, map<int, Ship>>> &mp) {
if (dir % 2 == 0) {
int val = shipCoord[ix].first + shipCoord[ix].second;
int key = shipCoord[ix].second;
mp[dir][val].erase(key);
} else {
int val = shipCoord[ix].first - shipCoord[ix].second;
int key = shipCoord[ix].first;
mp[dir][val].erase(key);
}
};
auto remove = [&](int ix) {
int curDir = shipDir[ix];
// remove from mp1, mp2
remDir1(curDir, ix, mp1);
remDir1((curDir - 1 + 4) % 4, ix, mp2);
// remove from mp3, mp4
if (curDir == 2 || curDir == 3) {
// removing from mp3
if (curDir == 2) {
mp3[curDir][shipCoord[ix].first].erase(shipCoord[ix].second);
} else {
mp3[curDir][shipCoord[ix].second].erase(shipCoord[ix].first);
}
} else {
// removing from mp4
if (curDir == 0) {
mp4[curDir][shipCoord[ix].first].erase(shipCoord[ix].second);
} else {
mp4[curDir][shipCoord[ix].second].erase(shipCoord[ix].first);
}
}
};
ll tprev = -1;
vector<pll> buffer;
auto clearBuffer = [&]() {
for (auto pr : buffer) {
// remove x and y from the maps
// each needs to be removed from mp1, mp2, and either mp3 or mp4
if (active[pr.first])
remove(pr.first);
if (active[pr.second])
remove(pr.second);
active[pr.first] = false;
active[pr.second] = false;
// ships were on the same diagonal
if ((shipDir[pr.second] - shipDir[pr.first] + 4) % 4 == 1) {
// check if the diagonal was x + pr.second or x - pr.second
if (shipDir[pr.first] % 2 == 0) {
auto it = mp1[shipDir[pr.first]].find(shipCoord[pr.first].first +
shipCoord[pr.first].second);
pushMp2(shipDir[pr.first], it);
} else {
auto it = mp1[shipDir[pr.first]].find(shipCoord[pr.first].first -
shipCoord[pr.first].second);
pushMp2(shipDir[pr.first], it);
}
} else {
// check if it was horizontal or vertical
if (shipDir[pr.first] == 2) {
auto it = mp3[shipDir[pr.first]].find(shipCoord[pr.first].first);
pushMp4(shipDir[pr.first], it);
} else {
auto it = mp3[shipDir[pr.first]].find(shipCoord[pr.first].second);
pushMp4(shipDir[pr.first], it);
}
}
}
};
while (!pq.empty()) {
auto [t, x, y] = pq.top();
if (t > tprev) {
clearBuffer();
buffer.clear();
} else {
pq.pop();
if (active[x] && active[y]) {
buffer.push_back({x, y});
}
}
tprev = t;
}
clearBuffer();
buffer.clear();
for (int i = 0; i < N; i++) {
if (active[i])
cout << i + 1 << "\n";
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
solve();
}
