#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
const int N = 5005;
int n, dead[N];
map<char, int> mp;
map<int, vector<pair<int, int>>> diag;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
char dir[4] = {'S', 'E', 'N', 'W'};
vector<pair<int, pair<int, int>>> edges, arr;
pair<int, int> move(int i, int m){
return {arr[i].S.F + dx[arr[i].F] * m, arr[i].S.S + dy[arr[i].F] * m};
}
int get_time(int i, int j){
if (arr[i].F == arr[j].F) return -1;
int X = abs(arr[i].S.F - arr[j].S.F);
int Y = abs(arr[i].S.S - arr[j].S.S);
if ((arr[i].F + 2) % 4 == arr[j].F)
X /= 2, Y /= 2;
auto [xi, yi] = move(i, max(X, Y));
auto [xj, yj] = move(j, max(X, Y));
if (xi == xj and yi == yj) return max(X, Y);
return -1;
}
int main(){
mp['S'] = 0, mp['E'] = 1, mp['N'] = 2, mp['W'] = 3;
cin >> n;
if (n <= 5000){
for (int i = 0; i < n; i ++){
dead[i] = 2e9;
int x, y;
char c;
cin >> x >> y >> c;
arr.push_back({mp[c], {x, y}});
for (int j = 0; j < i; j ++){
int t = get_time(i, j);
if (t == -1) continue;
edges.push_back({t, {i, j}});
}
}
sort(edges.begin(), edges.end());
for (int i = 0; i < edges.size(); i ++){
int j = i;
while (j + 1 < edges.size() and edges[j + 1].F == edges[i].F)
j++;
for (int k = i; k <= j; k ++){
auto [t, P] = edges[k];
auto [x, y] = P;
if (dead[x] < t or dead[y] < t) continue;
dead[x] = dead[y] = t;
}
i = j;
}
for (int i = 0; i < n; i ++)
if (dead[i] == 2e9)
cout << i + 1 << endl;
return 0;
}
for (int i = 0; i < n; i ++){
int x, y;
char c;
cin >> x >> y >> c;
arr.push_back({mp[c], {x, y}});
diag[x + y].push_back({x, i});
}
for (auto [di, vec] : diag){
sort(vec.begin(), vec.end());
vector<int> east_guys;
for (int i = 0; i < vec.size(); i ++){
auto [x, ind] = vec[i];
auto [c, P] = arr[ind];
if (c == 0){
if (east_guys.size())
east_guys.pop_back();
else
cout << ind + 1 << endl;
}
else{
east_guys.push_back(ind);
}
}
for (int x : east_guys)
cout << x + 1 << endl;
}
}
