// Author: Dan Skýpala
// O(X^2+NX) grid simulation
// Bit well optimized grid simulation where we check for collisions in grid.
#include <iostream>
#include <vector>
#include <unordered_map>
#include <utility>
using namespace std;
#pragma GCC optimize "Ofast"
struct xy_hash {
size_t operator () (const pair<int, int> &p) const {
return (p.first << 20) + p.second;
}
};
struct Ship {
int id;
int x;
int y;
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() {
x += dx;
y += dy;
}
pair<int, int> coords() {
return {x, y};
}
};
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<vector<int>> grid(max_x+1, vector<int>(max_y+1));
while (true) {
bool finished = true;
for (Ship s: ships) {
if (within_bounds(s)) {
finished = false;
}
}
if (finished) break;
for (int i=0; i < (int) ships.size(); i++) {
ships[i].move();
if (within_bounds(ships[i])) {
grid[ships[i].x][ships[i].y]++;
}
}
vector<Ship> remaining_ships;
for (Ship s: ships) {
if (!within_bounds(s) || grid[s.x][s.y] == 1) {
remaining_ships.push_back(s);
}
}
for (Ship s: ships) {
if (within_bounds(s))
grid[s.x][s.y] = 0;
}
ships = remaining_ships;
}
for (Ship s: ships) {
cout << s.id+1 << '\n';
}
}
