#include <bits/stdc++.h>
using namespace std;
struct ship {
int x, y, dir;
};
struct candidate {
int t, i, j;
bool operator < ( const candidate &x ) const {
if ( x.t == t ) {
if ( x.i == i )
return j < x.j;
return i < x.i;
}
return t < x.t;
}
};
const int MAX_N = 2e5;
const int N = 0;
const int S = 1;
const int V = 2;
const int E = 3;
bool alive[MAX_N];
unordered_map<int, set<pair<int, int>>> se, sv, ne, nv, ve, sn;
ship ships[MAX_N];
priority_queue<candidate> cand;
void insertShip( int i ) {
int x = ships[i].x, y = ships[i].y;
if ( ships[i].dir == S ) {
se[x + y].insert( { y, i } );
sv[x - y].insert( { y, i } );
sn[x].insert( { y, i } );
} else if ( ships[i].dir == N ) {
ne[x - y].insert( { y, i } );
nv[x + y].insert( { y, i } );
sn[x].insert( { y, i } );
} else if ( ships[i].dir == E ) {
se[x + y].insert( { y, i } );
ne[x - y].insert( { y, i } );
ve[y].insert( { x, i } );
} else {
sv[x - y].insert( { y, i } );
nv[x + y].insert( { y, i } );
ve[y].insert( { x, i } );
}
}
void eraseShip( int i ) {
int x = ships[i].x, y = ships[i].y;
if ( ships[i].dir == S ) {
se[x + y].erase( { y, i } );
sv[x - y].erase( { y, i } );
sn[x].erase( { y, i } );
} else if ( ships[i].dir == N ) {
ne[x - y].erase( { y, i } );
nv[x + y].erase( { y, i } );
sn[x].erase( { y, i } );
} else if ( ships[i].dir == E ) {
se[x + y].erase( { y, i } );
ne[x - y].erase( { y, i } );
ve[y].erase( { x, i } );
} else {
sv[x - y].erase( { y, i } );
nv[x + y].erase( { y, i } );
ve[y].erase( { x, i } );
}
}
void check( int d1, int d2, set<pair<int, int>> &s, int i, int x ) {
if ( ships[i].dir != d1 )
return;
if ( s.upper_bound( { x, i } ) == s.end() )
return;
int j = s.upper_bound( { x, i } )->second;
if ( ships[j].dir != d2 )
return;
cand.push( candidate{ -(abs( ships[j].x - ships[i].x ) + abs( ships[j].y - ships[i].y )) / 2, i, j } );
}
void getCand( int i ) {
int x = ships[i].x, y = ships[i].y;
check( E, V, ve[y], i, x );
check( S, N, sn[x], i, y );
check( S, E, se[x + y], i, y );
check( S, V, sv[x - y], i, y );
check( E, N, ne[x - y], i, y );
check( V, N, nv[x + y], i, y );
}
void refresh( int d1, int d2, set<pair<int, int>> &s, int i, int x ) {
if ( ships[i].dir != d1 )
return;
if ( s.upper_bound( { x, i } ) == s.begin() )
return;
auto p = s.upper_bound( { x, i } );
p--;
int j = p->second;
check( d1, d2, s, j, x );
}
void refreshCand( int i ) {
int x = ships[i].x, y = ships[i].y;
refresh( E, V, ve[y], i, x );
refresh( S, N, sn[x], i, y );
refresh( S, E, se[x + y], i, y );
refresh( S, V, sv[x - y], i, y );
refresh( E, N, ne[x - y], i, y );
refresh( V, N, nv[x + y], i, y );
}
int main() {
cin.tie( nullptr );
ios_base::sync_with_stdio( false );
int n;
cin >> n;
for ( int i = 0; i < n; i++ ) {
char dir;
cin >> ships[i].x >> ships[i].y >> dir;
ships[i].dir = (dir == 'N' ? N : (dir == 'S' ? S : (dir == 'E' ? E : V)));
insertShip( i );
alive[i] = true;
}
for ( int i = 0; i < n; i++ )
getCand( i );
//cout << "START " << cand.size() << "\n";
//for ( auto c: cand )
// cout << c.t << " " << c.i << " " << c.j << "\n";
while ( !cand.empty() ) {
candidate c = cand.top();
if ( !alive[c.i] || !alive[c.j] ) {
cand.pop();
continue;
}
vector<int> deadShips;
while ( !cand.empty() && cand.top().t == c.t ) {
c = cand.top();
cand.pop();
if ( !alive[c.i] || !alive[c.j] )
continue;
deadShips.push_back( c.i );
deadShips.push_back( c.j );
}
sort( deadShips.begin(), deadShips.end() );
deadShips.resize( unique( deadShips.begin(), deadShips.end() ) - deadShips.begin() );
for ( int i: deadShips ) {
alive[i] = false;
eraseShip( i );
}
for ( int i: deadShips )
refreshCand( i );
}
//cout << "FINISH\n";
for ( int i = 0; i < n; i++ ) {
if ( alive[i] )
cout << i + 1 << "\n";
}
return 0;
}
