#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using tlii = tuple<ll, int, int>;
using tiii = tuple<int, int, int>;
class ship{
public:
ll x;
ll y;
char d;
ship(ll a, ll b, char c)
{
x=a;
y=b;
d=c;
}
ship(bool take)
{
cin >> x >> y >> d;
}
ship()
{
//placeholder ship
x = 0; y = 0; d = 'N';
}
pll move(ll k)
{
if (d=='N')
return {x, y-k};
if (d=='S')
return {x, y+k};
if (d=='W')
return {x-k, y};
if (d=='E')
return {x+k, y};
return {x, y};
}
};
ll crash(ship ph, ship ch)
{
ll moves = abs(ph.x - ch.x) + abs(ph.y - ch.y);
moves = moves/2ll;
if (ph.move(moves) == ch.move(moves))
return moves;
return 0;
}
void process(vector<tiii> (&lin))
{
sort(lin.begin(), lin.end());
int k = lin.size();
stack<int> southerners;
for (int i=0; i<k; i++)
{
if (get<1>(lin[i]) == 1)
{
//dealing with an east ship
if (southerners.empty())
cout << get<2>(lin[i]) << '\n';
else
southerners.pop();
}
else
southerners.push(get<2>(lin[i]));
}
while (!southerners.empty())
{
cout << southerners.top() << '\n';
southerners.pop();
}
}
int main()
{
std::ios::sync_with_stdio(false);
int N;
cin >> N;
if (N<=5000)
{
vector<ship> fleet(N+1);
fleet[0] = ship();
for (int i=1; i<=N; i++)
fleet[i] = ship(1);
priority_queue<tlii, vector<tlii>, greater<tlii>> crash_and_burns;
for (int i=1; i<=N; i++)
for (int j=1; j<=N; j++)
{
ll x = crash(fleet[i], fleet[j]);
if (x != 0ll)
crash_and_burns.push({x, i, j});
}
vector<bool> alive(N+1, 1);
while (!crash_and_burns.empty())
{
vector<int> deaths;
ll tim = get<0>(crash_and_burns.top());
while ((!crash_and_burns.empty()) and (get<0>(crash_and_burns.top()) == tim))
{
int ph = get<1>(crash_and_burns.top());
int ch = get<2>(crash_and_burns.top());
crash_and_burns.pop();
if (alive[ph] and alive[ch])
{
deaths.push_back(ph);
deaths.push_back(ch);
}
}
int k = deaths.size();
for (int i=0; i<k; i++)
alive[deaths[i]] = 0;
}
for (int i=1; i<=N; i++)
if (alive[i])
cout << i << '\n';
}
else
{
//we assume all ships are S/E
map<ll, vector<tiii>> lines;
vector<ll> all_lines;
map<ll, bool> used_line;
for (int i = 1; i<=N; i++)
{
int x, y, z;
char d;
cin >> x >> y >> d;
if (d=='E')
z = 1;
else
z = 0;
lines[x+y].push_back({y, z, i});
all_lines.push_back(x+y);
}
for (int qq = 0; qq<N; qq++)
{
if (used_line[all_lines[qq]] == 0)
{
process(lines[all_lines[qq]]);
used_line[all_lines[qq]] = 1;
}
}
}
}
