// Author: Dan Skýpala
// O(N^2 log N) solution
// We generate all possible N^2 collisions and check in chronological order if they really happen.
#include <iostream>
#include <limits>
#include <vector>
#include <algorithm>
using namespace std;
#pragma GCC optimize "Ofast"
struct Ship {
int id;
int x;
int y;
int death_time = numeric_limits<int>::max();
int dx;
int dy;
Ship(int i, int x0, int y0, char d) {
id = i;
x = x0;
y = y0;
dx = d == 'W' ? -1 : (d == 'E' ? 1 : 0);
dy = d == 'N' ? -1 : (d == 'S' ? 1 : 0);
}
void move(int steps) {
x += dx*steps;
y += dy*steps;
}
pair<int, int> coords() {
return {x, y};
}
int collision_time(const Ship &s) {
int t = (abs(s.x - x) + abs(s.y - y)) / 2;
if (s.x + t*s.dx == x + t*dx && s.y + t*s.dy == y + t*dy) {
return t;
} else {
return numeric_limits<int>::max();
}
}
};
struct collision {
int time;
int i, j;
};
int n, max_x = 0, max_y = 0;
bool within_bounds(const Ship& s) {
return (0 <= s.x && s.x <= max_x) && (0 <= s.y && s.y <= max_y);
}
int main() {
cin >> n;
vector<Ship> ships;
for (int i=0; i<n; i++) {
int x, y; char d;
cin >> x >> y >> d;
max_x = max(max_x, x);
max_y = max(max_y, y);
ships.push_back({i, x, y, d});
}
vector<collision> collisions;
for (int i=0; i < (int) ships.size(); i++) {
for (int j=i+1; j < (int) ships.size(); j++) {
int col_time = ships[i].collision_time(ships[j]);
if (col_time < numeric_limits<int>::max()) {
collisions.push_back({col_time, i, j});
}
}
}
sort(collisions.begin(), collisions.end(), [](const collision& c1, const collision& c2){ return c1.time < c2.time; });
for (auto [time, i, j]: collisions) {
if (ships[i].death_time < time || ships[j].death_time < time)
continue; // One of the ships is already sunk
ships[i].death_time = ships[j].death_time = time;
}
for (Ship s: ships) {
if (s.death_time == numeric_limits<int>::max())
cout << s.id+1 << '\n';
}
}
