#include <bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pb push_back

void make_unq(vector<int> &x) {
    x.resize(unique(all(x)) - x.begin());
}

void solve() {
    int n; cin >> n;
    vector<vector<int>> a(n, vector<int>(3));
    map<char, int> ps;
    ps['N'] = 0; ps['W'] = 1; ps['E'] = 2; ps['S'] = 3;
    for (int i = 0; i < n; i++) {
        int x, y; char c; cin >> x >> y >> c;
        a[i] = {x, y, ps[c]};
    }

    auto dist = [&](int i, int j) -> int {
        if (a[i][2] == a[j][2]) return 2e9;
        if (a[i][2] + a[j][2] == 3) {
            if (a[i][2] == 0 || a[i][2] == 3) {
                if (a[i][0] == a[j][0] && (a[j][1] > a[i][1]) == (a[i][2] == 0)) {
                    return abs(a[i][1] - a[j][1]) / 2;
                } else return 2e9;
            }
            if (a[i][1] == a[j][1] && (a[i][0] < a[j][0]) == (a[i][2] == 2)) {
                return abs(a[i][0] - a[j][0]) / 2;
            }
            return 2e9;
        }
        if (a[i][2] == 1 || a[i][2] == 2) swap(i, j);
        if (a[i][2] == 0 && a[j][2] == 1) {
            if (a[i][0] - a[i][1] == a[j][0] - a[j][1] && a[i][0] < a[j][0]) return a[j][0] - a[i][0];
            return 2e9;
        }
        if (a[i][2] == 0 && a[j][2] == 2) {
            if (a[i][0] + a[i][1] == a[j][0] + a[j][1] && a[i][0] > a[j][0]) return a[i][0] - a[j][0];
            return 2e9;
        }
        if (a[i][2] == 3 && a[j][2] == 1) {
            if (a[i][0] + a[i][1] == a[j][0] + a[j][1] && a[j][0] > a[i][0]) {
                return a[j][0] - a[i][0];
            }
            return 2e9;
        }
        if (a[i][2] == 3 && a[j][2] == 2) {
            if (a[i][0] - a[i][1] == a[j][0] - a[j][1] && a[i][0] > a[j][0]) return a[i][0] - a[j][0];
            return 2e9;
        }
        return 0;
    };

    vector<int> alx, aly, alds, aldd;
    for (int i = 0; i < n; i++) {
        alx.pb(a[i][0]);
        aly.pb(a[i][1]);
        alds.pb(a[i][0] + a[i][1]);
        aldd.pb(a[i][0] - a[i][1]);
    }
    sort(all(alx)); sort(all(aly)); sort(all(alds)); sort(all(aldd));
    make_unq(alx); make_unq(aly); make_unq(alds); make_unq(aldd);
    map<int, int> posx, posy, posds, posdd;
    for (int i = 0; i < sz(alx); i++) posx[alx[i]] = i;
    for (int i = 0; i < sz(aly); i++) posy[aly[i]] = i;
    for (int i = 0; i < sz(alds); i++) posds[alds[i]] = i;
    for (int i = 0; i < sz(aldd); i++) posdd[aldd[i]] = i;
    vector<set<int>> xbyy(sz(aly)), ybyx(sz(alx)), xbydd(sz(aldd)), xbyds(sz(alds));
    map<pair<int, int>, int> ind;
    for (int i = 0; i < n; i++) ind[{a[i][0], a[i][1]}] = i;
    for (int i = 0; i < n; i++) {
        if (a[i][2] == 0 || a[i][2] == 3) {
            ybyx[posx[a[i][0]]].insert(a[i][1]);
        } else {
            xbyy[posy[a[i][1]]].insert(a[i][0]);
        }
        xbydd[posdd[a[i][0] - a[i][1]]].insert(a[i][0]);
        xbyds[posds[a[i][0] + a[i][1]]].insert(a[i][0]);
    }
    set<pair<int, pair<int, int>>> st;
    for (int i = 0; i < sz(alx); i++) {
        int prv = -1;
        for (auto &u : ybyx[i]) {
            int cur = ind[{alx[i], u}];
            if (prv != -1) {
                st.insert({dist(prv, cur), {prv, cur}});
            }
            prv = cur;
        }
    }
    for (int i = 0; i < sz(aly); i++) {
        int prv = -1;
        for (auto &u : xbyy[i]) {
            int cur = ind[{u, aly[i]}];
            if (prv != -1) {
                st.insert({dist(cur, prv), {prv, cur}});
            }
            prv = cur;
        }
    }
    for (int i = 0; i < sz(aldd); i++) {
        int prv = -1;
        for (auto &u : xbydd[i]) {
            int cur = ind[{u,u - aldd[i]}];
            if (prv != -1) {
                st.insert({dist(cur,prv),{prv,cur}});
            }
            prv=cur;
        }
    }
    for (int i = 0; i < sz(alds); i++) {
        int prv = -1;
        for (auto &u : xbyds[i]) {
            int cur= ind[{u, alds[i] - u}];
            if (prv != -1) {
                st.insert({dist(prv,cur),{prv,cur}});
            }
            prv=cur;
        }
    }
    auto del = [&](int i) {
        {
            int nxt=-1,prv=-1;
            auto it = xbyy[posy[a[i][1]]].find(a[i][0]);
            if (it != xbyy[posy[a[i][1]]].begin()) {
                auto it2=it;
                it2--;
                prv = ind[{*it2, a[i][1]}];
            }
            if (it != (--xbyy[posy[a[i][1]]].end())) {
                auto it2=it;
                it2++;
                nxt=ind[{*it2, a[i][1]}];
            }
            if (nxt != -1) {
                st.erase({dist(i, nxt), {i, nxt}});
            }
            if (prv != -1) {
                st.erase({dist(i, prv), {i, prv}});
            }
            if (nxt != -1 && prv != -1) {
                st.insert({dist(prv,nxt), {prv, nxt}});
            }
        }
        {
            int nxt=-1,prv=-1;
            auto it = ybyx[posx[a[i][0]]].find(a[i][1]);
            if (it != ybyx[posx[a[i][0]]].begin()) {
                auto it2=it;
                it2--;
                prv = ind[{a[i][0], *it2}];
            }
            if (it != (--ybyx[posx[a[i][0]]].end())) {
                auto it2=it;
                it2++;
                nxt=ind[{a[i][0], *it2}];
            }
            if (nxt != -1) {
                st.erase({dist(i, nxt), {i, nxt}});
            }
            if (prv != -1) {
                st.erase({dist(i, prv), {i, prv}});
            }
            if (nxt != -1 && prv != -1) {
                st.insert({dist(prv,nxt), {prv, nxt}});
            }
        }
        {
            int nxt=-1,prv=-1;
            auto it = xbydd[posdd[a[i][0]-a[i][1]]].find(a[i][0]);
            if (it != xbydd[posdd[a[i][0]-a[i][1]]].begin()) {
                auto it2=it;
                it2--;
                prv = ind[{*it2, *it2 - a[i][0] + a[i][1]}];
            }
            if (it != (--xbydd[posdd[a[i][0]-a[i][1]]].end())) {
                auto it2=it;
                it2++;
                nxt=ind[{*it2, *it2 - a[i][0] + a[i][1]}];
            }
            if (nxt != -1) {
                st.erase({dist(i, nxt), {i, nxt}});
            }
            if (prv != -1) {
                st.erase({dist(i, prv), {i, prv}});
            }
            if (nxt != -1 && prv != -1) {
                st.insert({dist(prv,nxt), {prv, nxt}});
            }
        }
        {
            int nxt=-1,prv=-1;
            auto it = xbyds[posds[a[i][0] + a[i][1]]].find(a[i][0]);
            if (it != xbyds[posds[a[i][0] + a[i][1]]].begin()) {
                auto it2=it;
                it2--;
                prv = ind[{*it2, a[i][0]+a[i][1]-*it2}];
            }
            if (it != (--xbyds[posds[a[i][0] + a[i][1]]].end())) {
                auto it2=it;
                it2++;
                nxt=ind[{*it2, a[i][0]+a[i][1]-*it2}];
            }
            if (nxt != -1) {
                st.erase({dist(i, nxt), {i, nxt}});
            }
            if (prv != -1) {
                st.erase({dist(i, prv), {i, prv}});
            }
            if (nxt != -1 && prv != -1) {
                st.insert({dist(prv,nxt), {prv, nxt}});
            }
        }
    };  
    vector<int> alive(n,1);
    while (!st.empty() && (*st.begin()).first < 2e9) {
        unordered_set<int> todel;
        int cur = (*st.begin()).first;
        while (!st.empty() && (*st.begin()).first == cur) {
            todel.insert((*st.begin()).second.first);
            todel.insert((*st.begin()).second.second);
            st.erase(st.begin());
        }
        for (auto &u : todel) {
            alive[u] = 0;
            del(u);
        }
    }
    for (int i = 0; i < n; i++) {
        if (alive[i]) cout << i + 1 << '\n';
    }
}

signed main() {
    int tt = 1;
    #ifdef LOCAL 
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
        cin >> tt;
    #endif

    for (int i = 0; i < tt; i++) {
        solve();
    }

    return 0;
}