#pragma GCC optimize("Ofast","unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define int long long
enum direction{
north,
south,
east,
west,
};
enum slant{
diff,
sum,
headon,
};
struct ship{
int x,y;
direction d;
};
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin >> N;
vector<ship> ships(N+1);
vector shipLookup(4,vector<map<int,set<pair<int,int>>>>(3));
for(int i=1;i<=N;i++){
char d;
cin >> ships[i].x >> ships[i].y >> d;
switch(d){
case 'S': ships[i].d = north; break;
case 'N': ships[i].d = south; break;
case 'E': ships[i].d = east; break;
case 'W': ships[i].d = west; break;
}
shipLookup[ships[i].d][diff][ships[i].x-ships[i].y].emplace(ships[i].x,i);
shipLookup[ships[i].d][sum][ships[i].x+ships[i].y].emplace(ships[i].x,i);
if(ships[i].d == north or ships[i].d==south){
shipLookup[ships[i].d][headon][ships[i].x].emplace(ships[i].y,i);
} else {
shipLookup[ships[i].d][headon][ships[i].y].emplace(ships[i].x,i);
}
}
priority_queue<pair<int,int>> pq;
auto getCollision = [&](ship boat){
pair<int,vector<int>> ans = {1e12,{}};
auto addJustAfter = [&](direction d,slant s){
pair<int,int> q;
int idx,l;
if(s==diff){
idx = boat.x-boat.y;
l=boat.x;
}
if(s==sum){
idx = boat.x + boat.y;
l = boat.x;
}
if(s==headon){
if(d==north or d==south){
idx = boat.x;
l = boat.y;
} else {
idx = boat.y;
l = boat.x;
}
}
auto iter = shipLookup[d][s][idx].upper_bound({l,0ll});
if(iter!=shipLookup[d][s][idx].end()){
q.second = iter->second;
q.first = (abs(boat.x-ships[q.second].x)+abs(boat.y-ships[q.second].y))/2ll;
if(q.first<ans.first){ans.second.clear();ans.first=q.first;}
if(q.first==ans.first)ans.second.emplace_back(q.second);
}
};
auto addJustBefore = [&](direction d,slant s){
pair<int,int> q;
int idx,l;
if(s==diff){
idx = boat.x-boat.y;
l=boat.x;
}
if(s==sum){
idx = boat.x + boat.y;
l = boat.x;
}
if(s==headon){
if(d==north or d==south){
idx = boat.x;
l = boat.y;
} else {
idx = boat.y;
l = boat.x;
}
}
auto iter = shipLookup[d][s][idx].upper_bound({l,0ll});
if(iter!=shipLookup[d][s][idx].begin()){
iter--;
q.second = iter->second;
q.first = (abs(boat.x-ships[q.second].x)+abs(boat.y-ships[q.second].y))/2ll;
if(q.first<ans.first){ans.second.clear();ans.first=q.first;}
if(q.first==ans.first)ans.second.emplace_back(q.second);
}
};
if(boat.d==north){
addJustAfter(west,diff);
addJustBefore(east,sum);
addJustAfter(south,headon);
}
if(boat.d==south){
addJustAfter(west,sum);
addJustBefore(east,diff);
addJustBefore(north,headon);
}
if(boat.d==east){
addJustAfter(south,diff);
addJustAfter(north,sum);
addJustAfter(west,headon);
}
if(boat.d==west){
addJustBefore(south,sum);
addJustBefore(north,diff);
addJustBefore(east,headon);
}
return ans;
};
auto eraseShip = [&](int i){
shipLookup[ships[i].d][diff][ships[i].x-ships[i].y].erase({ships[i].x,i});
shipLookup[ships[i].d][sum][ships[i].x+ships[i].y].erase({ships[i].x,i});
if(ships[i].d == north or ships[i].d==south){
shipLookup[ships[i].d][headon][ships[i].x].erase({ships[i].y,i});
} else {
shipLookup[ships[i].d][headon][ships[i].y].erase({ships[i].x,i});
}
};
vector<bool> visited(N+1);
function<bool(int,int)> dfs = [&](int x,int tim){
visited[x]=true;
eraseShip(x);
while(true){
auto t = getCollision(ships[x]);
if(t.first>=tim){
return true;
}
bool works = false;
for(int&i:t.second)if(dfs(i,t.first)){
works=true;
}
if(works){
return false;
}
}
};
for(int i=1;i<=N;i++)if(!visited[i]){
if(dfs(i,1e10)){
cout << i << '\n';
}
}
}
