// Naval Battle
// CEOI 2024 Day 1
// 100 points submission
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
using P = pair<int, int>;
#define x first
#define y second
int n;
P pos[202020];
char d[202020];
const int NEVER = 1999999999 + 7;
bool gone[202020];
vector<set<P>> enemyCollection;
int getNewSet() {
int z = enemyCollection.size();
enemyCollection.push_back(set<P>());
return z;
}
int crashCheckLow(int pos, int sid) {
// fprintf(stderr, " Opponent Set: %d\n", sid);
while(!enemyCollection[sid].empty()) {
auto it = enemyCollection[sid].lower_bound({pos, -1});
if(it == enemyCollection[sid].begin()) return NEVER;
it--;
int idx = (*it).second;
if(gone[idx]) {
enemyCollection[sid].erase(it);
} else {
return pos - (*it).first;
}
}
return NEVER;
}
int crashCheckHigh(int pos, int sid) {
// fprintf(stderr, " Opponent Set: %d\n", sid);
while(!enemyCollection[sid].empty()) {
auto it = enemyCollection[sid].upper_bound({pos, 303030});
if(it == enemyCollection[sid].end()) return NEVER;
int idx = (*it).second;
if(gone[idx]) {
enemyCollection[sid].erase(it);
} else {
return (*it).first - pos;
}
}
return NEVER;
}
class OpponentInfo {
public:
int myPos;
char myTeam;
int sid;
OpponentInfo() {}
};
vector<OpponentInfo> opponents[202020];
int getCrashTime(int idx) {
int earliest = NEVER;
for(OpponentInfo O: opponents[idx]) {
// fprintf(stderr, "Check Crash Time of ship %d\n", idx + 1);
int thisRound = NEVER;
if(O.myTeam == 'L') {
thisRound = crashCheckHigh(O.myPos, O.sid);
} else {
thisRound = crashCheckLow(O.myPos, O.sid);
}
earliest = min(earliest, thisRound);
}
return earliest;
}
priority_queue<P> ICU;
int nextEvent[202020];
void preProcessSUM(const vector<P> &ships) {
if(ships.size() <= 1) return;
const int NORTH_SET = getNewSet();
const int SOUTH_SET = getNewSet();
const int WEST_SET = getNewSet();
const int EAST_SET = getNewSet();
int z = ships.size();
for(int i = 0; i < z; i++) {
int idx = ships[i].second;
int pos = ships[i].first;
OpponentInfo info;
info.myPos = pos;
if(d[idx] == 'N') {
enemyCollection[NORTH_SET].insert({pos, idx});
info.sid = WEST_SET;
info.myTeam = 'L';
} else if(d[idx] == 'W') {
enemyCollection[WEST_SET].insert({pos, idx});
info.sid = NORTH_SET;
info.myTeam = 'R';
////
} else if(d[idx] == 'S') {
enemyCollection[SOUTH_SET].insert({pos, idx});
info.sid = EAST_SET;
info.myTeam = 'R';
} else if(d[idx] == 'E') {
enemyCollection[EAST_SET].insert({pos, idx});
info.sid = SOUTH_SET;
info.myTeam = 'L';
}
opponents[idx].push_back(info);
}
}
void preProcessDIFF(const vector<P> &ships) {
if(ships.size() <= 1) return;
const int NORTH_SET = getNewSet();
const int SOUTH_SET = getNewSet();
const int WEST_SET = getNewSet();
const int EAST_SET = getNewSet();
int z = ships.size();
// fprintf(stderr, "%d ships to consider\n", z);
for(int i = 0; i < z; i++) {
int idx = ships[i].second;
int pos = ships[i].first;
OpponentInfo info;
info.myPos = pos;
if(d[idx] == 'N') {
enemyCollection[NORTH_SET].insert({pos, idx});
info.sid = EAST_SET;
info.myTeam = 'R';
} else if(d[idx] == 'E') {
enemyCollection[EAST_SET].insert({pos, idx});
info.sid = NORTH_SET;
info.myTeam = 'L';
////
} else if(d[idx] == 'W') {
enemyCollection[WEST_SET].insert({pos, idx});
info.sid = SOUTH_SET;
info.myTeam = 'R';
} else if(d[idx] == 'S') {
enemyCollection[SOUTH_SET].insert({pos, idx});
info.sid = WEST_SET;
info.myTeam = 'L';
}
opponents[idx].push_back(info);
}
}
void preProcessLine(const vector<P> &ships) {
if(ships.size() <= 1) return;
const int LOW_SET = getNewSet();
const int HIGH_SET = getNewSet();
int z = ships.size();
// fprintf(stderr, "%d ships to consider\n", z);
for(int i = 0; i < z; i++) {
int idx = ships[i].second;
int pos = ships[i].first;
// fprintf(stderr, "(Ship %d, Pos = %d)\n", idx + 1, pos);
OpponentInfo info;
info.myPos = pos / 2;
if(d[idx] == 'S' || d[idx] == 'E') {
// increase coordinate by 1 (team LOW)
enemyCollection[LOW_SET].insert({pos / 2, idx});
info.myTeam = 'L';
info.sid = HIGH_SET;
} else if(d[idx] == 'N' || d[idx] == 'W') {
// decrease coordinate by 1 (team HIGH)
enemyCollection[HIGH_SET].insert({pos / 2, idx});
info.myTeam = 'R';
info.sid = LOW_SET;
}
opponents[idx].push_back(info);
}
}
void processEvent(const int t) {
// {{ Event on top of ICU is actually going to happen at time t }}
set<int> eliminated;
while(!ICU.empty()) {
int claim = -ICU.top().first;
int idx = ICU.top().second;
if(claim != t) break;
ICU.pop();
int actual = getCrashTime(idx);
if(actual == t) {
// Yes!
eliminated.insert(idx);
} else {
if(actual < NEVER) {
ICU.push({-actual, idx});
}
}
}
for(int u: eliminated) gone[u] = true;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for(int i = 0; i < n; i++) {
cin >> pos[i].x >> pos[i].y;
string s; cin >> s;
d[i] = s[0];
// fprintf(stderr, "Registered Ship %d at (%d, %d) [%c]\n", i + 1, pos[i].x, pos[i].y, d[i]);
}
// Prepare Initial Crash
map<int, vector<P>> sumBank, diffBank, xBank, yBank;
for(int i = 0; i < n; i++) {
sumBank[pos[i].x + pos[i].y].push_back({pos[i].x, i});
diffBank[pos[i].x - pos[i].y].push_back({pos[i].x, i});
if(d[i] == 'N' || d[i] == 'S') xBank[pos[i].x].push_back({pos[i].y, i});
if(d[i] == 'E' || d[i] == 'W') yBank[pos[i].y].push_back({pos[i].x, i});
}
for(auto it = sumBank.begin(); it != sumBank.end(); it++) preProcessSUM(it->second);
for(auto it = diffBank.begin(); it != diffBank.end(); it++) preProcessDIFF(it->second);
for(auto it = xBank.begin(); it != xBank.end(); it++) preProcessLine(it->second);
for(auto it = yBank.begin(); it != yBank.end(); it++) preProcessLine(it->second);
// Start the Battle
for(int i = 0; i < n; i++) {
nextEvent[i] = getCrashTime(i);
if(nextEvent[i] < NEVER) {
ICU.push({-nextEvent[i], i});
}
// fprintf(stderr, "Preliminary[Ship %d]: crash at t = %d\n", i + 1, nextEvent[i]);
}
while(!ICU.empty()) {
int claim = -ICU.top().first;
int idx = ICU.top().second;
// Re-Evaluation
int actual = getCrashTime(idx);
if(actual == claim) {
processEvent(actual);
} else {
ICU.pop();
if(actual < NEVER) {
ICU.push({-actual, idx});
}
}
}
// Final Answer
for(int i = 0; i < n; i++) if(!gone[i]) cout << (i + 1) << "\n";
return 0;
}
