#include <bits/stdc++.h>
using namespace std;
struct Ship {
int index;
int x, y;
char dir;
bool alive = true;
};
pair<int, int> move_ship(int x, int y, char d) {
if (d == 'N') return {x, y - 1};
if (d == 'S') return {x, y + 1};
if (d == 'E') return {x + 1, y};
return {x - 1, y}; // 'W'
}
int main() {
int N;
cin >> N;
vector<Ship> ships(N);
for (int i = 0; i < N; ++i) {
cin >> ships[i].x >> ships[i].y >> ships[i].dir;
ships[i].index = i + 1;
}
bool changed = true;
// We'll simulate up to 500 steps, that's enough for this grid
for (int step = 0; step < 500 && changed; ++step) {
changed = false;
map<pair<int, int>, vector<int>> position_map;
// Move all alive ships and collect their new positions
for (int i = 0; i < N; ++i) {
if (!ships[i].alive) continue;
auto [new_x, new_y] = move_ship(ships[i].x, ships[i].y, ships[i].dir);
ships[i].x = new_x;
ships[i].y = new_y;
position_map[{new_x, new_y}].push_back(i);
}
// Check for collisions
for (auto& [pos, ids] : position_map) {
if (ids.size() > 1) {
changed = true;
for (int id : ids) {
ships[id].alive = false;
}
}
}
}
// Output surviving ships
for (auto& ship : ships) {
if (ship.alive) {
cout << ship.index << '\n';
}
}
return 0;
}
