#include <bits/stdc++.h>

using namespace std;
    
typedef long long ll;
const int  N = 2e5 + 12, MOD = (int)1e9 + 7;

int n;
map<int,set<array<int,3>>> v[4],h[4],d[4],db[4];
bool dead[N];
int conv(char dir) {
    if(dir == 'N') {
        return 0;
    } else if(dir == 'E') {
        return 1;
    } else if(dir == 'S') {
        return 2;
    }
    return 3;
}
void add(int x,int y,int dir,int i) {
    if(dir == 1 || dir == 3) {
        h[dir][y].insert({x,y,i});
    } else {
        v[dir][x].insert({x,y,i});
    }
    d[dir][x + y].insert({x,y,i});
    db[dir][x - y].insert({x,y,i});
}
int cur[N];
set<pair<int,int>> st;
void del(int x,int y,int dir,int i) {
    dead[i] = 1;
    st.erase({cur[i],i});
    if(dir == 1 || dir == 3) {
        h[dir][y].erase({x,y,i});
    } else {
        v[dir][x].erase({x,y,i});
    }
    d[dir][x + y].erase({x,y,i});
    db[dir][x - y].erase({x,y,i});
}
int x[N],y[N],dir[N];
const int inf = (int)1e9 + 2;
const int dx[] = {0,1,0,-1},dy[] = {-1,0,1,0};
int dist(int i,int j) {
    if(i == j || j == -1) return inf;
    int ret = abs(x[i] - x[j]) / 2 + abs(y[i] - y[j]) / 2;
    int x1 = x[i] + dx[dir[i]] * ret,y1 = y[i] + dy[dir[i]] * ret;
    int x2 = x[j] + dx[dir[j]] * ret,y2 = y[j] + dy[dir[j]] * ret;
    return (x1 == x2 && y1 == y2 ? ret : inf);
}
int nx(set<array<int,3>> &st,int i){
    array<int,3> f = {x[i],y[i],i};
    auto it = st.lower_bound(f);
    if(it == st.end()) return -1;
    return (*it)[2];
}
int prev(set<array<int,3>> &st,int i) {
    array<int,3> f = {x[i],y[i],i};
    auto it = st.lower_bound(f);
    if(it == st.begin()) return -1;
    it--;
    return (*it)[2];
}
int calc(int i) {
    int ret = inf;
    for(int j = 1;j <= n;j++) {
        if(!dead[j]) {
            ret = min(ret,dist(i,j));
        }
    }
    return ret;
    for(int k = 0;k < 4;k++) {
        if(dir[i] == k) continue;
        if(dir[i] % 2 == k % 2) {
            if(k % 2 == 1) {
                int j = nx(h[k][y[i]],i);
                ret = min(ret,dist(i,j));   
                j = prev(h[k][y[i]],i);
                ret = min(ret,dist(i,j)); 
            } else {
                int j = nx(v[k][x[i]],i);
                ret = min(ret,dist(i,j));   
                j = prev(v[k][x[i]],i);
                ret = min(ret,dist(i,j)); 
            }
        } else {
            {
                int j = nx(d[k][x[i] + y[i]],i);
                ret = min(ret,dist(i,j));   
                j = prev(d[k][x[i] + y[i]],i);
                ret = min(ret,dist(i,j)); 
            }
            {
                int j = nx(db[k][x[i] - y[i]],i);
                ret = min(ret,dist(i,j));   
                j = prev(db[k][x[i] - y[i]],i);
                ret = min(ret,dist(i,j)); 
            }
        }
    }
    return ret;
}
map<array<int,3>,int> id;
void test() {
    cin >> n;
    for(int i = 1;i <= n;i++) {
        char di;
        cin >> x[i] >> y[i] >> di;
        dir[i] = conv(di);
        add(x[i],y[i],dir[i],i);
        st.insert({0,i});
        id[{x[i],y[i],dir[i]}] = i;
    }
    while(!st.empty()) {
        auto [val,v] = (*st.begin());
        if(val == inf) {
            break;
        }
        st.erase(st.begin());
        int _ = calc(v);
        assert(_ >= val);
        if(val != _) {
            cur[v] = _;
            st.insert({_,v});
            continue;
        }
        int x1 = x[v] + dx[dir[v]] * val,y1 = y[v] + dy[dir[v]] * val;
        for(int i = 0;i < 4;i++) {
            int X = x1 + dx[i],Y = y1 +dy[i];
            int d;
            if(i % 2 == 0) {
                d = 2 - i;
            } else {
                d = 4 - i;
            }
            if(id.count({X,Y,d})) {
                del(X,Y,d,id[{X,Y,d}]);
            }
        }
    }
    for(auto [x,y]:st) {
        cout << y << '\n';
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t = 1; 
    // cin >> t;
    while(t--) {
        test();
    }
}