#include <bits/stdc++.h> using namespace std; #define ll int #define pii pair<ll, ll> #define fi first #define sec second #pragma GCC optimise ("o-fast", "unroll-loops"); const ll INF = 1e9; const int MAXN = 2e5; ll X[MAXN + 5], Y[MAXN + 5]; char dir[MAXN + 5]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); ll N; cin >> N; vector <ll> compress; vector <ll> idx(26), dead(N + 5); idx['U' - 'A'] = 0; idx['D' - 'A'] = 1; idx['L' - 'A'] = 2; idx['R' - 'A'] = 3; for (int i = 1; i <= N; i++) { cin >> X[i] >> Y[i] >> dir[i]; compress.push_back(X[i]); compress.push_back(Y[i]); compress.push_back(X[i] + Y[i]); compress.push_back(X[i] - Y[i]); if (dir[i] == 'N') dir[i] = 'U'; else if (dir[i] == 'S') dir[i] = 'D'; else if (dir[i] == 'W') dir[i] = 'L'; else if (dir[i] == 'E') dir[i] = 'R'; } vector <ll> positive(N + 5), negative(N + 5), horizontal(N + 5), vertical(N + 5); sort(compress.begin(), compress.end()); compress.erase(unique(compress.begin(), compress.end()), compress.end()); ll M = compress.size(); vector <vector<set<pii>>> pos(4, vector<set<pii>> (M + 5)); vector <vector<set<pii>>> neg(4, vector<set<pii>> (M + 5)); vector <vector<set<pii>>> hori(4, vector<set<pii>> (M + 5)); vector <vector<set<pii>>> verti(4, vector<set<pii>> (M + 5)); auto get_id = [&](ll idx) { return lower_bound(compress.begin(), compress.end(), idx) - compress.begin() + 1; }; for (int i = 1; i <= N; i++) { positive[i] = get_id(X[i] + Y[i]); negative[i] = get_id(X[i] - Y[i]); horizontal[i] = get_id(Y[i]); vertical[i] = get_id(X[i]); pos[idx[dir[i] - 'A']][positive[i]].insert({X[i], i}); neg[idx[dir[i] - 'A']][negative[i]].insert({X[i], i}); if (dir[i] == 'L' || dir[i] == 'R') hori[idx[dir[i] - 'A']][horizontal[i]].insert({X[i], i}); if (dir[i] == 'U' || dir[i] == 'D') verti[idx[dir[i] - 'A']][vertical[i]].insert({Y[i], i}); } priority_queue <pair<ll, pii>> pq; auto id = [&](char c) { return idx[c - 'A']; }; auto add = [&](ll idx) { if (dir[idx] == 'U') { // cek D auto x = verti[id('D')][vertical[idx]].lower_bound({Y[idx], -1}); if (x != verti[id('D')][vertical[idx]].begin()) { --x; pq.push({-(abs(Y[idx] - (*x).fi) / 2), {idx, (*x).sec}}); } // cek positive x = pos[id('L')][positive[idx]].upper_bound({X[idx], -1}); if (x != pos[id('L')][positive[idx]].end()) { pq.push({-abs(X[idx] - (*x).fi), {idx, (*x).sec}}); } // cek negative x = neg[id('R')][negative[idx]].lower_bound({X[idx], -1}); if (x != neg[id('R')][negative[idx]].begin()) { --x; pq.push({-abs(X[idx] - (*x).fi), {idx, (*x).sec}}); } } else if (dir[idx] == 'D') { // cek U auto x = verti[id('U')][vertical[idx]].lower_bound({Y[idx], -1}); if (x != verti[id('U')][vertical[idx]].end()) { pq.push({-(abs(Y[idx] - (*x).fi) / 2), {idx, (*x).sec}}); } // cek positive x = pos[id('R')][positive[idx]].lower_bound({X[idx], -1}); if (x != pos[id('R')][positive[idx]].begin()) { --x; pq.push({-abs(X[idx] - (*x).fi), {idx, (*x).sec}}); } // cek negative x = neg[id('L')][negative[idx]].upper_bound({X[idx], -1}); if (x != neg[id('L')][negative[idx]].end()) { pq.push({-abs(X[idx] - (*x).fi), {idx, (*x).sec}}); } } else if (dir[idx] == 'R') { // cek L auto x = hori[id('L')][horizontal[idx]].upper_bound({X[idx], -1}); if (x != hori[id('L')][horizontal[idx]].end()) { pq.push({-(abs(X[idx] - (*x).fi) / 2), {idx, (*x).sec}}); } // cek positive x = pos[id('D')][positive[idx]].upper_bound({X[idx], -1}); if (x != pos[id('D')][positive[idx]].end()) { pq.push({-abs(X[idx] - (*x).fi), {idx, (*x).sec}}); } // cek negative x = neg[id('U')][negative[idx]].upper_bound({X[idx], -1}); if (x != neg[id('U')][negative[idx]].end()) { pq.push({-abs(X[idx] - (*x).fi), {idx, (*x).sec}}); } } else { // cek R auto x = hori[id('R')][horizontal[idx]].lower_bound({X[idx], -1}); if (x != hori[id('R')][horizontal[idx]].begin()) { --x; pq.push({-(abs(X[idx] - (*x).fi) / 2), {idx, (*x).sec}}); } // cek positive x = pos[id('U')][positive[idx]].upper_bound({X[idx], -1}); if (x != pos[id('U')][positive[idx]].begin()) { --x; pq.push({-abs(X[idx] - (*x).fi), {idx, (*x).sec}}); } // cek negative x = neg[id('D')][negative[idx]].upper_bound({X[idx], -1}); if (x != neg[id('D')][negative[idx]].begin()) { --x; pq.push({-abs(X[idx] - (*x).fi), {idx, (*x).sec}}); } } }; auto del = [&](ll i) { pos[idx[dir[i] - 'A']][positive[i]].erase({X[i], i}); neg[idx[dir[i] - 'A']][negative[i]].erase({X[i], i}); if (dir[i] == 'L' || dir[i] == 'R') hori[idx[dir[i] - 'A']][horizontal[i]].erase({X[i], i}); if (dir[i] == 'U' || dir[i] == 'D') verti[idx[dir[i] - 'A']][vertical[i]].erase({Y[i], i}); }; for (int i = 1; i <= N; i++) { add(i); } while (!pq.empty()) { ll lst = -1; vector <pii> op; while (!pq.empty() && (lst == -1 || pq.top().fi == -lst)) { op.push_back({pq.top().sec.fi, pq.top().sec.sec}); lst = -pq.top().fi; pq.pop(); } // cout << lst << "\n"; vector <ll> v; for (auto [i, j] : op) { if (dead[i] || dead[j]) { if (!dead[i]) add(i); if (!dead[j]) add(j); } else { del(i), del(j); v.push_back(i); v.push_back(j); } } for (auto i : v) dead[i] = 1; } for (int i = 1; i <= N; i++) { if (!dead[i]) cout << i << "\n"; } } /* */