#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
//#define int long long
#define pb push_back
#define s second
#define f first
#define pf push_front
#define inf 100000000000000000
#define bitebi __builtin_popcountll
#define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
#define YES cout <<"YES\n"
#define NO cout << "NO\n"
#define debug cout << "Here Fine" << endl ;
#define pr pair < int , int >
#define fbo find_by_order // returns iterator
#define ook order_of_key // returns strictly less numbers than key
using namespace std ;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
using namespace __gnu_pbds;
using namespace __gnu_cxx;
template<class T> using ordered_set =tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update> ;
const double Pi=acos(-1.0);
const double EPS=1E-8;
const int mod = 1000000007 ;
const int mod1 = 998244353 ;
const int N = 2e5 + 10 ;
mt19937 R(time(0));
map < int , int > ma , ma1 ;
struct Point {
int x;
int y;
};
Point val[ N ] ;
bool willIntersect(Point p1, char d1, Point p2, char d2, int &time) {
// Calculate deltas for movement
int dx1 = (d1 == 'E') ? 1 : (d1 == 'W') ? -1 : 0;
int dy1 = (d1 == 'N') ? -1 : (d1 == 'S') ? 1 : 0;
int dx2 = (d2 == 'E') ? 1 : (d2 == 'W') ? -1 : 0;
int dy2 = (d2 == 'N') ? -1 : (d2 == 'S') ? 1 : 0;
// Relative movement per time step
int rel_dx = dx2 - dx1;
int rel_dy = dy2 - dy1;
// Initial difference in positions
int diff_x = p1.x - p2.x;
int diff_y = p1.y - p2.y;
//cout << rel_dx << " " << rel_dy << " " << diff_x << " " << diff_y << endl ;
if (rel_dx != 0 && diff_x % rel_dx == 0) {
time = diff_x / rel_dx;
if (time >= 0 && diff_y == time * rel_dy) {
return true;
}
} else if (rel_dy != 0 && diff_y % rel_dy == 0) {
time = diff_y / rel_dy;
if (time >= 0 && diff_x == time * rel_dx) {
return true;
}
} else if (rel_dx == 0 && rel_dy == 0) {
if (diff_x == 0 && diff_y == 0) {
time = 0;
return true;
}
}
// No intersection found
return false;
}
int n ;
vector < pair < int , pair < int , int > > > v ;
int ds[ N ] ;
char c[ N ] ;
void solve(){
cin >> n ;
FOR( i , n ) cin >> val[ i ].x >> val[ i ].y >> c[ i ] ;
FOR( i , n ) ds[ i ] = -1 ;
FOR( i , n ){
for( int j = i + 1 ; j < n ; j ++ ){
// check if they coincide
if( c[ i ] == c[ j ] ) continue ;
int time = -1 ;
if( willIntersect(val[ i ], c[ i ], val[ j ], c[ j ], time) ){
time = abs( time ) ;
v.pb( { time , { i , j } } ) ;
// cout << i << " " << j << " time " << time << endl;
}
}
}
sort( v.begin() , v.end() ) ;
for( auto x : v ){
if( ds[ x.s.f ] != -1 && ds[ x.s.s ] != -1 ) continue ;
if( ds[ x.s.f ] == -1 && ds[ x.s.s ] == -1 ){
ds[ x.s.f ] = x.f ;
ds[ x.s.s ] = x.f ; continue ;
}
if( ds[ x.s.f ] == -1 ){
if( ds[ x.s.s ] == x.f ) ds[ x.s.f ] = x.f ;
}
else{
if( ds[ x.s.f ] == x.f ) ds[ x.s.s ] = x.f ;
}
}
FOR( i , n ){
if( ds[ i ] == -1 ) cout << i + 1 << " " ;
}
return ;
}
signed main() {
ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
int t = 1 ; // cin >> t ;
while( t -- ){
solve() ;
}
}
