#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<typename T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef map<pair<int, char>, VI> LINE;
struct SHIP {
int x, y;
char d;
int ind;
void move(int s) {
if (d == 'N') y -= s;
else if (d == 'E') x += s;
else if (d == 'S') y += s;
else if (d == 'W') x -= s;
}
int limit(LINE& sum, LINE& dif, LINE& xmp, LINE& ymp) {
int ret = +2e9;
VI::iterator it;
PII p;
auto calclower = [&](LINE& line, int val, bool divide = false) {
if ((it = lower_bound(all(line[p]), val)) != line[p].begin()) {
int cur = val - *prev(it);
if (divide) cur /= 2;
setmin(ret, cur);
}
};
auto calcupper = [&](LINE& line, int val, bool divide = false) {
if ((it = upper_bound(all(line[p]), val)) != line[p].end()) {
int cur = *it - val;
if (divide) cur /= 2;
setmin(ret, cur);
}
};
if (d == 'N') {
p = {x+y, 'W'};
calcupper(sum, x);
p = {x-y, 'E'};
calclower(dif, x);
p = {x, 'S'};
calclower(xmp, y, true);
} else if (d == 'E') {
p = {x+y, 'S'};
calcupper(sum, x);
p = {x-y, 'N'};
calcupper(dif, x);
p = {y, 'W'};
calcupper(ymp, x, true);
} else if (d == 'S') {
p = {x+y, 'E'};
calclower(sum, x);
p = {x-y, 'W'};
calcupper(dif, x);
p = {x, 'N'};
calcupper(xmp, y, true);
} else if (d == 'W') {
p = {x+y, 'N'};
calclower(sum, x);
p = {x-y, 'S'};
calclower(dif, x);
p = {y, 'E'};
calclower(ymp, x, true);
}
return ret;
}
};
int minstep(vector<SHIP> a) {
int n = a.size();
LINE sum;
LINE dif;
LINE xmp;
LINE ymp;
for (auto[x, y, d, ind] : a) {
sum[{x+y, d}].pb(x);
dif[{x-y, d}].pb(x);
xmp[{x, d}].pb(y);
ymp[{y, d}].pb(x);
}
for (auto& p : sum) sort(all(p.ss));
for (auto& p : dif) sort(all(p.ss));
for (auto& p : xmp) sort(all(p.ss));
for (auto& p : ymp) sort(all(p.ss));
int ret = +2e9;
for (auto p : a) {
int cur = p.limit(sum, dif, xmp, ymp);
/*cout << "CUR: " << cur << endl;*/
setmin(ret, cur);
}
return ret;
}
void removesink(vector<SHIP>& a) {
map<PII, int> cnt;
for (auto[x, y, d, ind] : a) cnt[{x, y}]++;
vector<SHIP> b;
for (auto[x, y, d, ind] : a) {
if (cnt[{x, y}] == 1) {
b.pb({x, y, d, ind});
}
}
a = b;
}
void solve() {
int n;
cin >> n;
vector<SHIP> a(n);
rep(i, n) {
auto&[x, y, d, ind] = a[i];
cin >> x >> y;
cin >> d;
ind = i+1;
}
while (true) {
int step = minstep(a);
if (step == +2e9) break;
for (auto& p : a) p.move(step);
removesink(a);
}
for (auto[x, y, d, ind] : a) cout << ind << endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
/*freopen("mincross.in", "r", stdin); */
/*freopen("test.out", "w", stdout); */
int t = 1;
/*cin >> t; */
while (t--) solve();
}
