#include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; #define ordered_set tree<pair<int, int>, null_type,less<pair<int, int>>, rb_tree_tag,tree_order_statistics_node_update> #define ll long long #define MOD 1000000007 #define MAXN 2e5 #define SIZE 314 #define pb push_back using namespace std; ll power(ll a, ll b){ if (b == 0) return 1; ll res = power(a, b / 2); // if (b % 2 == 1) return res * res % MOD * a % MOD; // return res * res % MOD; if (b % 2 == 1) return res * res * a; return res * res; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; map<string, pair<int, int>> dir; vector<tuple<int, int, string>> nums(n); for (int i = 0; i < n; i++){ int x, y; string d; cin >> x >> y >> d; nums[i] = {x, y, d}; } dir["N"] = {0, -1}; dir["E"] = {1, 0}; dir["S"] = {0, 1}; dir["W"] = {-1, 0}; vector<pair<bool, int>> exist(n, pair<bool, int>(1, -1)); vector<tuple<int, int, int>> stuf; for (int i = 0; i < n; i++){ for (int j = i + 1; j < n; j++){ int time = (abs(get<0>(nums[i]) - get<0>(nums[j])) + abs(get<1>(nums[i]) - get<1>(nums[j]))) / 2; stuf.pb({time, i, j}); } } sort(stuf.begin(), stuf.end()); for (auto &num : stuf){ auto [time, i, j] = num; if (!exist[i].first && !exist[j].first) continue; int x1 = get<0>(nums[i]) + dir[get<2>(nums[i])].first * time; int y1 = get<1>(nums[i]) + dir[get<2>(nums[i])].second * time; int x2 = get<0>(nums[j]) + dir[get<2>(nums[j])].first * time; int y2 = get<1>(nums[j]) + dir[get<2>(nums[j])].second * time; if (x1 == x2 && y1 == y2){ if (exist[i].first && exist[j].first){ exist[i].first = 0; exist[j].first = 0; exist[i].second = time; exist[j].second = time; } else{ if (!exist[i].first && exist[i].second == time){ exist[j].first = 0; exist[j].second = time; } else if (!exist[j].first && exist[j].second == time){ exist[i].first = 0; exist[i].second = time; } } } } for (int i = 0; i < n; i++){ if (exist[i].first) cout << i + 1 << "\n"; } return 0; }