#include <bits/stdc++.h>
using namespace std;
struct ship
{
int x, y;
char type;
int dirx, diry, i;
};
istream &operator>>(istream &is, ship &s)
{
is >> s.x >> s.y >> s.type;
if (s.type == 'E')
s.dirx = 1, s.diry = 0;
if (s.type == 'W')
s.dirx = -1, s.diry = 0;
if (s.type == 'S')
s.dirx = 0, s.diry = 1;
if (s.type == 'N')
s.dirx = 0, s.diry = -1;
return is;
}
bool operator<(ship a, ship b)
{
if (a.x + a.y == b.x + b.y)
return a.x < b.x;
return a.x + a.y < b.x + b.y;
}
bool operator==(ship a, ship b) { return (a.x == b.x && a.y == b.y); }
struct colision
{
int time;
ship a, b;
};
bool operator<(colision a, colision b) { return a.time > b.time; }
bool operator==(colision a, colision b) { return (a.time == b.time && a.a == b.a && a.b == b.b); }
colision colide(ship a, ship b)
{
if (a.type == b.type)
return {1000000001, a, b};
if (a.dirx == 0 && b.dirx == 0 && ((a.y < b.y && a.diry == 1) || (a.y > b.y && a.diry == -1)) && a.x == b.x)
return {abs(a.y - b.y) / 2, a, b};
if (a.diry == 0 && b.diry == 0 && ((a.x < b.x && a.dirx == 1) || (a.x > b.x && a.dirx == -1)) && a.y == b.y)
return {abs(a.x - b.x) / 2, a, b};
if (a.diry == 0)
swap(a, b);
if (((a.y < b.y && a.diry == 1) || (a.y > b.y && a.diry == -1)) && ((b.x < a.x && b.dirx == 1) || (b.x > a.x && b.dirx == -1)) && abs(a.x - b.x) == abs(a.y - b.y))
return {abs(a.x - b.x), a, b};
return {1000000001, a, b};
}
struct diagonal
{
list<ship> ships;
map<ship, list<ship>::iterator> M;
priority_queue<colision> colisions;
void push_back(ship s)
{
M[s] = ships.end();
ships.push_back(s);
M[s]--;
auto pos = M[s];
if (ships.size() == 1)
return;
pos--;
colisions.push(colide(*pos, s));
}
colision get()
{
colision ans = colisions.top();
colisions.pop();
validate();
return ans;
}
void validate()
{
while (!colisions.empty() && (!M.count(colisions.top().a) || !M.count(colisions.top().b)))
colisions.pop();
}
void remove(ship s)
{
if (M.count(s) == 0)
return;
auto pos = M[s], pos2 = M[s];
if (pos != ships.begin() && pos != ships.end())
colisions.push(colide(*--pos, *++pos2));
ships.erase(M[s]);
M.erase(s);
validate();
}
};
struct ensemble
{
int type = 1, type2 = 1;
int hash(int x, int y) { return type2 * x + type * y; }
map<int, diagonal> M;
priority_queue<pair<colision, int>> colisions;
void validate()
{
while (!colisions.empty() && (M[colisions.top().second].colisions.empty() || !(colisions.top().first == M[colisions.top().second].colisions.top())))
colisions.pop();
}
colision get()
{
if (colisions.empty())
return {1000000001};
int pos = colisions.top().second;
colision ans = M[pos].get();
colisions.push({M[pos].colisions.top(), pos});
validate();
return ans;
}
void add(ship s)
{
int pos = hash(s.x, s.y);
M[pos].push_back(s);
if (!M[pos].colisions.empty())
colisions.push({M[pos].colisions.top(), pos});
}
void remove(ship s)
{
int pos = hash(s.x, s.y);
M[pos].remove(s);
if (!M[pos].colisions.empty())
colisions.push({M[pos].colisions.top(), pos});
validate();
}
};
int find(int x, vector<int> &r)
{
if (x == r.size())
return x;
return (r[x] == x) ? x : r[x] = find(r[x], r);
}
int main()
{
int N;
cin >> N;
int SW = 0, SE = 1, NW = 2, NE = 3, NS = 4, WE = 5;
vector<ensemble> Tab(6);
Tab[SW].type = -1, Tab[NE].type = -1, Tab[NS].type = 0, Tab[WE].type2 = 0;
vector<ship> ships(N), V, H;
for (int i = 0; i < N; i++)
{
cin >> ships[i];
ships[i].i = i;
ship s = ships[i];
V.push_back(s);
H.push_back(s);
}
sort(V.begin(), V.end(), [&](ship a, ship b)
{ return a.y < b.y; });
sort(H.begin(), H.end(), [&](ship a, ship b)
{ return a.x < b.x; });
for (int i = 0; i < N; i++)
{
if (V[i].dirx == 0)
Tab[NS].add(V[i]);
if (H[i].diry == 0)
Tab[WE].add(H[i]);
if (H[i].dirx == 1 || H[i].diry == 1)
Tab[SE].add(H[i]);
if (H[i].dirx == 1 || H[i].diry == -1)
Tab[NE].add(H[i]);
if (H[i].dirx == -1 || H[i].diry == -1)
Tab[NW].add(H[i]);
if (H[i].dirx == -1 || H[i].diry == 1)
Tab[SW].add(H[i]);
}
vector<int> alive(N, 1000000001);
while (true)
{
int minn = 1000000001;
for (int i = 0; i < 6; i++)
if (!Tab[i].colisions.empty())
minn = min(minn, Tab[i].colisions.top().first.time);
vector<ship> removed;
if (minn == 1000000001)
break;
for (int i = 0; i < 6; i++)
{
while (!Tab[i].colisions.empty() && Tab[i].colisions.top().first.time == minn)
{
colision cur = Tab[i].get();
alive[cur.a.i] = minn;
alive[cur.b.i] = minn;
removed.push_back(cur.a);
removed.push_back(cur.b);
}
}
while (!removed.empty())
{
for (int i = 0; i < 6; i++)
Tab[i].remove(removed.back());
removed.pop_back();
}
}
for (int i = 0; i < N; i++)
if (alive[i] == 1000000001)
cout << i + 1 << '\n';
}
