#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 1e6 + 5;
int read(){
    int flag = 1;
	int res = 0;
	char c = getchar();
	for (;!isdigit(c); c = getchar())
        if (c == '-')
            flag = -1;
	for (;isdigit(c); c = getchar())
        res = (res << 1) + (res << 3) + (c ^ 48);
    return res * flag;
}
struct Information{
    int minAns, idL, idR;
    int leftPos, leftId, rightPos, rightId;
    Information(){
        minAns = 1e16;
        leftPos = -1e16, rightPos = 1e16;
        leftId = 0, rightId = 0;
        idL = 0, idR = 0;
    }
    Information (int pos, int type, int id){
        minAns = 1e16;
        leftPos = -1e16, rightPos = 1e16;
        leftId = 0, rightId = 0;
        idL= 0, idR = 0;
        if (type == 0)
            leftPos = pos, leftId = id;
        else
            rightPos = pos, rightId = id;
    }
    friend Information operator + (Information x, Information y){
        Information res;
        res.minAns = min({x.minAns, y.minAns, y.rightPos - x.leftPos});
        if (x.minAns == res.minAns)
            res.idL = x.idL, res.idR = x.idR;
        else if (y.minAns == res.minAns)
            res.idL = y.idL, res.idR = y.idR;
        else
            res.idL = x.leftId, res.idR = y.rightId;
        res.leftPos = max(x.leftPos, y.leftPos);
        if (x.leftPos == res.leftPos)
            res.leftId = x.leftId;
        else
            res.leftId = y.leftId;
        res.rightPos = min(x.rightPos, y.rightPos);
        if (x.rightPos == res.rightPos)
            res.rightId = x.rightId;
        else
            res.rightId = y.rightId;
        return res;
    }
};
class SegmentTree{
private:
    const static int MAXNODE = 4 * MAXN;
    #define ls (id << 1)
    #define rs (id << 1 | 1)
    struct Node{
        int L, R;
        Information info;
    }t[MAXNODE];
    void update(int id){
        t[id].info = t[ls].info + t[rs].info;
    }
    void buildTree(int id, int L, int R){
        t[id].L = L, t[id].R = R;
        if (L == R){
            t[id].info = initialVal[L];
            return;
        };
        int mid = (L + R) >> 1;
        buildTree(ls, L, mid);
        buildTree(rs, mid + 1, R);
        update(id);
    }
    void change(int id, int pos, Information info){
        if (t[id].L == t[id].R){
            t[id].info = info;
            return;
        }
        if (pos <= t[ls].R)
            change(ls, pos, info);
        else
            change(rs, pos, info);
        update(id);
    }
    Information query(int id, int l, int r){
        if (t[id].L == l && t[id].R == r)
            return t[id].info;
        if (r <= t[ls].R)
            return query(ls, l, r);
        else if (l >= t[rs].L)
            return query(rs, l, r);
        else
            return query(ls, l, t[ls].R) + query(rs, t[rs].L, r);
    }
public:
    Information initialVal[MAXN];
    void buildTree(int n){
        buildTree(1, 1, n);
    }
    void change(int pos, Information info){
        change(1, pos, info);
    }
    Information query(int l, int r){
        if (l > r)
            return Information();
        return query(1, l, r);
    }
}tree[6];
struct Node{
    int x, y, a, id;
}t[MAXN];
bool cmp1(Node a, Node b){
    if (a.x + a.y == b.x + b.y)
        return a.x < b.x;
    return a.x + a.y < b.x + b.y;
}
bool cmp2(Node a, Node b){
    if (a.x - a.y == b.x - b.y)
        return a.x < b.x;
    return a.x - a.y < b.x - b.y;
}
bool cmp3(Node a, Node b){
    if (a.x == b.x)
        return a.y < b.y;
    return a.x < b.x;
}
bool cmp4(Node a, Node b){
    if (a.y == b.y)
        return a.x < b.x;
    return a.y < b.y;
}
bool cmp5(Node a, Node b){
    return a.id < b.id;
}
struct Segment{
    int l, r, x;
}seg[6 * MAXN];
int segId[6][MAXN];
int id[6][MAXN];
int type[6][4]{
    {1, 0, -1, -1}, 
    {-1, 0, 1, -1},
    {-1, -1, 0, 1},
    {0, -1, -1, 1},
    {0, -1, 1, -1},
    {-1, 0, -1, 1}
};
struct Plan{
    int time, x, y, z;
    bool operator < (const Plan T) const{
        return time > T.time;
    }
};
priority_queue <Plan> q;
int getNum(Node a, int x){
    if (x == 4)
        return a.y / 2;
    else if (x == 5)
        return a.x / 2;
    else
        return a.x;
}
int vis[MAXN];
void push(int i, int l, int r, bool debug = false){
    Information res = tree[i].query(l, r);
    if (res.minAns >= 1e12)
        return;
    q.push({res.minAns, res.idL, res.idR, i});
}
int cnt = 0;
void getAllId(int n){
    sort(t + 1, t + n + 1, cmp1);
    t[n + 1].x = 1e16, t[n + 1].y = 0;
    for (int i = 1, lst = 1; i <= n; i++){
        id[0][t[i].id] = id[2][t[i].id] = i;
        if (t[i].x + t[i].y != t[i + 1].x + t[i + 1].y){
            seg[++cnt] = {lst, i, 0};
            for (int j = lst; j <= i; j++)
                segId[0][t[j].id] = segId[2][t[j].id] = cnt;
            lst = i + 1;
        }
    }
    sort(t + 1, t + n + 1, cmp2);
    t[n + 1].x = 1e16, t[n + 1].y = 0;
    for (int i = 1, lst = 1; i <= n; i++){
        id[1][t[i].id] = id[3][t[i].id] = i;
        if (t[i].x - t[i].y != t[i + 1].x - t[i + 1].y){
            seg[++cnt] = {lst, i, 1};
            for (int j = lst; j <= i; j++)
                segId[1][t[j].id] = segId[3][t[j].id] = cnt;
            lst = i + 1;
        }
    }
    sort(t + 1, t + n + 1, cmp3);
    t[n + 1].x = 1e16;
    for (int i = 1, lst = 1; i <= n; i++){
        id[4][t[i].id] = i;
        if (t[i].x != t[i + 1].x){
            seg[++cnt] = {lst, i, 4};
            for (int j = lst; j <= i; j++)
                segId[4][t[j].id] = cnt;
            lst = i + 1;
        }
    }
    sort(t + 1, t + n + 1, cmp4);
    t[n + 1].y = 1e16;
    for (int i = 1, lst = 1; i <= n; i++){
        id[5][t[i].id] = i;
        if (t[i].y != t[i + 1].y){
            seg[++cnt] = {lst, i, 5};
            for (int j = lst; j <= i; j++)
                segId[5][t[j].id] = cnt;
            lst = i + 1;
        }
    }
}
void init(int n){
    sort(t + 1, t + n + 1, cmp5);
    for (int i = 1; i <= n; i++){
        for (int j = 0; j < 6; j++){
            if (type[j][t[i].a] == -1)
                continue;
            tree[j].initialVal[id[j][i]] = Information(getNum(t[i], j), type[j][t[i].a], i);
        }
    }
    for (int i = 0; i < 6; i++)
        tree[i].buildTree(n);
    for (int i = 1; i <= cnt; i++){
        auto [l, r, x] = seg[i];
        push(x, l, r);
        if (x == 0 || x == 1)
            push(x + 2, l, r);
    }
}
vector <int> vec;
void solve(int x, int i){
    tree[i].change(id[i][x], Information());
    auto [l, r, useless] = seg[segId[i][x]];
    push(i, l, r);
    vec.push_back(x);
}
void applyChange(){
    for (auto x: vec){
        for (int i = 0; i < 6; i++){
            if (type[i][t[x].a] != -1)
                tree[i].change(id[i][x], Information());
            auto [l, r, useless] = seg[segId[i][x]];
            push(i, l, r);
        }
    }
    vec.clear();
}
signed main(){
    int n = read();
    for (int i = 1; i <= n; i++){
        t[i].x = read(), t[i].y = read(), t[i].id = i;
        char c;
        cin >> c;
        if (c == 'S')
            t[i].a = 0;
        else if (c == 'E')
            t[i].a = 1;
        else if (c == 'N')
            t[i].a = 2;
        else
            t[i].a = 3;
    }
    getAllId(n);
    init(n);
    int oldTime = 0;
    while (!q.empty()){
        auto [tim, x, y, i] = q.top();
        q.pop();
        if (tim != oldTime){
            applyChange();
        }
        if (tim >= 1e12)
            break;
        if ((vis[x] != 0 && vis[x] < tim) || (vis[y] != 0 && vis[y] < tim))
            continue;
        if (!vis[x])
            solve(x, i), vis[x] = tim;
        if (!vis[y])
            solve(y, i), vis[y] = tim;
        oldTime = tim;
    }
    for (int i = 1; i <= n; i++)
        if (!vis[i])
            cout << i << endl;
    return 0;
}