#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <bits/extc++.h>
#include <unistd.h>
#include <fcntl.h>
using namespace std;
using namespace __gnu_pbds;
template<size_t BUFSIZE=1<<16>
class Scanner{
private:
char buf[BUFSIZE];
char* it;
char* ed;
const int fd;
Scanner(const Scanner&) = delete;
Scanner& operator=(const Scanner&) = delete;
void flush(){
if(it==ed){
ed=buf+read(fd,buf,BUFSIZE);
it=buf;
}
}
void ss(){
flush();
while(*it<=32){++it;flush();}
}
void scan(char& x){ss();x=*(it++);}
void scan(string& x){
do{
ss();
char * itbg=it;
while(it!=ed&&*it>32)++it;
x.append(itbg,it);
} while(it==ed);
}
template<typename T> void scan_u(T& x){
ss();
x=0;
do{
x=T(x*10+*(it++)-'0');
flush();
} while(*it>32);
}
template<typename T> void scan_i(T& x){
ss();
x=0;
bool sign=0;
if(*it=='-'){
sign=1;
++it;
flush();
}
do{
x=T(x*10+*(it++)-'0');
flush();
} while(*it>32);
if(sign)x=T(-x);
}
template<typename T> void scan_f(T& x){
ss();
x=0;
bool sign=0;
if(*it=='-'){
sign=1;
++it;
flush();
}
while(*it>32 && *it!='.'){
x=x*T(10.0)+T(*(it++)-'0');
flush();
}
if(*it=='.'){
++it;
flush();
T e=T(0.1);
while(*it>32){
x=x+e*T(*(it++)-'0');
e=e*T(0.1);
flush();
};
}
if(sign)x=-x;
}
void scan(int8_t& x){scan_i(x);}
void scan(int16_t& x){scan_i(x);}
void scan(int32_t& x){scan_i(x);}
void scan(int64_t& x){scan_i(x);}
void scan(long long& x){scan_i(x);}
void scan(uint8_t& x){scan_u(x);}
void scan(uint16_t& x){scan_u(x);}
void scan(uint32_t& x){scan_u(x);}
void scan(uint64_t& x){scan_u(x);}
void scan(unsigned long long& x){scan_u(x);}
void scan(float& x){double d; scan_f(d); x=d;}
void scan(double& x){scan_f(x);}
void scan(long double& x){scan_f(x);}
template<typename T> void scan(T& x){for(auto &i:x)scan(i);}
public:
~Scanner(){}
Scanner(const int _fd=0):it(0),ed(0),fd(_fd){}
void operator()(){}
template<typename T, typename...R>
void operator()(T& a,R&...rest){
scan(a);
operator()(rest...);
}
};
template<size_t BUFSIZE=1<<16>
class Printer {
private:
char buf[BUFSIZE];
char* it;
const int fd;
void fif(const size_t x){
if(size_t(BUFSIZE+buf-it)<x)flush();
}
void print(const char x){fif(1);*(it++)=x;}
void print(char* const x){
size_t s = strlen(x);
if(s>BUFSIZE/2){
flush();
write(fd,x,s);
} else {
fif(s);
copy(x,x+s,it);
it+=s;
}
}
void print(const char* const x){print((char*)x);}
void print(const string& x){
if(x.size()>BUFSIZE/2){
flush();
write(fd,x.data(),x.size());
} else {
fif(x.size());
copy(x.begin(),x.end(),it);
it+=x.size();
}
}
template<typename T> void print_u(T x){
constexpr size_t siz = size_t(sizeof(T) * log10(256)) + 1;
uint8_t i=siz;
char b[siz];
do {
b[--i]=char(x%10+'0');
x=T(x/10);
}while(x);
fif(siz-i);
copy(b+i,b+siz,it);
it+=siz-i;
}
template<typename T> void print_i(T x){
constexpr size_t siz = size_t(sizeof(T) * log10(256)) + 2;
size_t i=siz;
char b[siz];
const bool neg=(x<0);
if(neg)x=-x;
do {
b[--i]=char(x%10+'0');
x=T(x/10);
}while(x);
if(neg)b[--i]='-';
fif(siz-i);
copy(b+i,b+siz,it);
it+=siz-i;
}
void print_f(const double x){
const uint64_t d = *((uint64_t*)&x);
const bool neg = d>>63;
int32_t e = (d>>52)&((1ull<<11)-1);
uint64_t m = d&((1ull<<52)-1);
if(e){
e-=1075;
m+=(1ull<<52);
} else e=-1074ll;
int32_t re=e;
if(e<0){
while(e++){
if(m&0xe000000000000000){
m>>=1;
re++;
} else m*=5;
}
} else {
while(e--){
if(m&0x8000000000000000) m/=5;
else {
m<<=1;
re--;
}
}
}
if(neg)print('-');
print(m);
print('e');
print(re);
}
void print(int8_t x){print_i(x);}
void print(int16_t x){print_i(x);}
void print(int32_t x){print_i(x);}
void print(int64_t x){print_i(x);}
void print(long long x){print_i(x);}
void print(uint8_t x){print_u(x);}
void print(uint16_t x){print_u(x);}
void print(uint32_t x){print_u(x);}
void print(uint64_t x){print_u(x);}
void print(unsigned long long x){print_u(x);}
void print(const float x){print_f(x);}
void print(const double x){print_f(x);}
void print(const long double x){print_f(x);}
template<typename T> void print(const T& x){
for(auto &i:x){
print(i);
print(' ');
}
}
public:
~Printer(){flush();}
Printer(const int _fd=1):it(buf),fd(_fd){}
void flush(){
write(fd,buf,it-buf);
it=buf;
}
void operator()(){}
template<typename T, typename...R>
void operator()(T&& a,R&&...rest){
print(a);
operator()(rest...);
}
};
struct Ship {
int x, y;
char dir;
int dist(const Ship &o) const { return abs(x - o.x) + abs(y - o.y); }
};
enum { N, E, S, W };
int dir_num(char dir) {
switch (dir) {
case 'N': return N;
case 'E': return E;
case 'S': return S;
case 'W': return W;
}
}
#define LEFT(dir, card, repr, discr) \
it = (dir)[card][repr].lower_bound(discr); \
if (it != (dir)[card][repr].begin() && !(dir)[card][repr].empty()) \
add_crash(ship, prev(it)->second);
#define RIGHT(dir, card, repr, discr) \
it = (dir)[card][repr].upper_bound(discr); \
if (it != (dir)[card][repr].end()) \
add_crash(ship, it->second);
Scanner<> scan;
Printer<> prnt;
int main() {
int n; scan(n);
vector<Ship> ships(n);
for (auto &[x, y, dir]: ships)
scan(x, y, dir);
gp_hash_table<int, map<int, int>> hor[4], ver[4], diagp[4], diagm[4];
for (int i = 0; i < n; i++) {
auto [x, y, dir] = ships[i];
int d = dir_num(dir);
hor[d][y][x] = i;
ver[d][x][y] = i;
diagp[d][x + y][x] = i;
diagm[d][x - y][x] = i;
}
map<int, vector<pair<int, int>>> crashes;
auto add_crash = [&](int u, int v) {
crashes[ships[u].dist(ships[v])].emplace_back(u, v);
};
auto next_crash = [&](int ship) {
auto [x, y, dir] = ships[ship];
vector<int> crashes;
map<int, int>::iterator it;
switch (dir) {
case 'N':
LEFT(ver, S, x, y);
LEFT(diagm, E, x - y, x);
RIGHT(diagp, W, x + y, x);
return;
case 'E':
RIGHT(hor, W, y, x);
RIGHT(diagp, S, x + y, x);
return;
case 'S':
RIGHT(diagm, W, x - y, x);
return;
}
};
for (int i = 0; i < n; i++) {
next_crash(i);
}
vector<bool> alive(n, true);
while (!crashes.empty()) {
gp_hash_table<int, null_type> boomships;
for (auto &[x, y]: crashes.begin()->second) {
if (!alive[x] || !alive[y]) continue;
boomships.insert(x);
boomships.insert(y);
}
for (auto ship: boomships) {
alive[ship] = false;
auto [x, y, dir] = ships[ship];
int d = dir_num(dir);
hor[d][y].erase(x);
ver[d][x].erase(y);
diagp[d][x + y].erase(x);
diagm[d][x - y].erase(x);
for (auto dir: {hor, ver, diagp, diagm}) {
for (int card = 0; card < 4; card++) {
int discr = dir == ver ? y : x;
int repr;
if (dir == hor) repr = y;
if (dir == ver) repr = x;
if (dir == diagp) repr = x + y;
if (dir == diagm) repr = x - y;
{
auto it = dir[card][repr].upper_bound(discr);
if (it != dir[card][repr].end()) {
next_crash(it->second);
}
}
{
auto it = dir[card][repr].lower_bound(discr);
if (it != dir[card][repr].begin() && !dir[card][repr].empty()) {
next_crash(prev(it)->second);
}
}
}
}
}
crashes.erase(crashes.begin());
}
for (int i = 0; i < n; i++)
if (alive[i])
prnt(i + 1, '\n');
}
