#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;
using ll = long long;
const int N = 200'000 + 10;
const int INF = 1'000'000'000;
struct Ship {
int x, y;
int dir;
int idx, dir_x, dir_y;
Ship() {};
Ship(int _x, int _y, char _dir, int _idx) : x(_x), y(_y), dir(-1), idx(_idx), dir_x(-1), dir_y(-1) {
if (_dir == 'N') dir = 0, dir_x = 0, dir_y = -1;
else if (_dir == 'S') dir = 3, dir_x = 0, dir_y = 1;
else if (_dir == 'E') dir = 2, dir_x = 1, dir_y = 0;
else if (_dir == 'W') dir = 1, dir_x = -1, dir_y = 0;
};
int encounter(const Ship& other) const {
assert(this->dir >= other.dir);
if (this->dir == other.dir) return INF;
if (this->dir == 3 - other.dir) {
// S - N or E - W
if (this->dir == 3) {
if (this->x != other.x || this->y > other.y) return INF;
// cùng tính chẵn lẻ nên chắc chắn sẽ giao nhau
return (other.y - this->y) / 2;
}
if (this->dir == 2) {
if (this->y != other.y || this->x > other.x) return INF;
// cùng tính chẵn lẻ nên chắc chắn sẽ giao nhau
return (other.x - this->x) / 2;
}
assert(false);
}
if (this->dir == 3) {
if (other.dir == 2) {
/*
S(3)
!
!
E(2)--->
*/
if (this->x <= other.x || this->y >= other.y) return INF;
int dist_x = this->x - other.x;
int dist_y = other.y - this->y;
if (dist_x != dist_y) return INF;
return dist_x;
} else if (other.dir == 1) {
/*
S(3)
!
!
<---W(1)
*/
if (this->x >= other.x || this->y >= other.y) return INF;
int dist_x = other.x - this->x;
int dist_y = other.y - this->y;
if (dist_x != dist_y) return INF;
return dist_x;
}
assert(false);
}
if (this->dir == 2) {
if (other.dir == 0) {
/*
E(2)--->
!
!
N(0)
*/
if (this->x >= other.x || this->y >= other.y) return INF;
int dist_x = other.x - this->x;
int dist_y = other.y - this->y;
if (dist_x != dist_y) return INF;
return dist_x;
}
assert(false);
}
if (this->dir == 1) {
if (other.dir == 0) {
/*
<---W(1)
!
!
N(0)
*/
if (this->x <= other.x || this->y >= other.y) return INF;
int dist_x = this->x - other.x;
int dist_y = other.y - this->y;
if (dist_x != dist_y) return INF;
return dist_x;
}
assert(false);
}
assert(false);
};
void add(int dist) {
x += dist * dir_x;
y += dist * dir_y;
}
bool operator>(const Ship& other) const {
return this->dir > other.dir;
}
};
int n;
vector<Ship> ships;
namespace sub4 {
bool check() {
return (n <= 200);
}
bool mark[N];
void solve() {
while (!ships.empty()) {
int dist_encounter = INF;
for (int i = 0; i < ships.size(); ++i) {
for (int j = i + 1; j < ships.size(); ++j) {
Ship l = ships[i], r = ships[j];
if (r > l) swap(l, r);
int dist = l.encounter(r);
// if (i == 2 && j == 3) {
// cerr << dist << '\n';
// }
if (dist_encounter > dist) {
dist_encounter = dist;
}
}
}
for (int i = 0; i < ships.size(); ++i) {
for (int j = i + 1; j < ships.size(); ++j) {
Ship l = ships[i], r = ships[j];
if (r > l) swap(l, r);
int dist = l.encounter(r);
if (dist == dist_encounter) {
mark[l.idx] = mark[r.idx] = true;
}
}
}
if (dist_encounter >= INF) break;
vector<Ship> newShips;
for (auto& ship : ships) {
if (mark[ship.idx]) continue;
ship.add(dist_encounter);
newShips.push_back(ship);
}
ships = move(newShips);
}
for (const auto &ship : ships) cout << ship.idx << '\n';
}
}
namespace sub5 {
int mark[N];
void solve() {
for (int i = 1; i <= n; ++i) mark[i] = INF;
vector<tuple<int, int, int>> events;
for (int i = 0; i < ships.size(); ++i) {
for (int j = i + 1; j < ships.size(); ++j) {
Ship l = ships[i], r = ships[j];
if (r > l) swap(l, r);
int dist = l.encounter(r);
if (dist >= INF) continue;
events.push_back(make_tuple(dist, l.idx, r.idx));
}
}
sort(events.begin(), events.end());
for (int i = 0, j = 0; i < events.size(); i = j) {
while (j < events.size() && get<0>(events[i]) == get<0>(events[j])) ++j;
for (int k = i; k < j; ++k) {
const auto& [dist, l, r] = events[k];
if (mark[l] < dist || mark[r] < dist) {
continue;
}
mark[l] = mark[r] = dist;
}
}
for (int i = 1; i <= n; ++i) {
if (mark[i] >= INF) {
cout << i << '\n';
}
}
}
}
int32_t main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr); std::cout.tie(nullptr);
cin >> n;
ships.reserve(n);
for (int i = 1; i <= n; ++i) {
int x, y; char dir; cin >> x >> y >> dir;
ships.push_back(Ship(x, y, dir, i));
}
sub5::solve();
return (0 ^ 0);
}
/// Code by vuavisao
