Problem: Example

Input

2 10 6
4 4 E
6 4 W


Output

2

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define DEBUG(x) cerr << #x << " = " << x << endl
#define int long long
const int INF = (int)1e9;
int N, W, D;
vector<int> X, Y;
vector<char> F;
vector<pair<int, int>> getInterval() {
  vector<pair<int, int>> ret;
  REP(i,N) {
    int left, right;
    if(F[i] == 'N') {
      left = 2*W + D + (D - Y[i]) + X[i];
      right = W + Y[i] - (W - X[i]);
    }
    else if(F[i] == 'S') {
      left = W + Y[i] + (W - X[i]);
      right = 2*W + D + (D - Y[i]) - X[i];
    }
    else if(F[i] == 'E') {
      left = W + Y[i] - (W - X[i]);
      right = W + Y[i] + (W - X[i]);
    }
    else if(F[i] == 'W') {
      left = 2*W + D + (D - Y[i]) - X[i];
      right = 2*W + D + (D - Y[i]) + X[i];
    }
    else {
      assert(false);
    }
    pair<int, int> ans;
    ans.first = (left + 2*W + 2*D) % (2*W + 2*D);
    ans.second = (right + 2*W + 2*D) % (2*W + 2*D);
    ret.push_back(ans);
  }
  return ret;
}
struct BIT {
  int N;
  vector<int> data;
  BIT(int n) : N(n), data(n + 1, 0) {}
  void add(int a, int w) {
    ++a;
    for(int x = a; x <= N; x += x & -x) {
      data[x] += w;
    }
  }
  int sum(int a) {
    int ret = 0;
    for(int x = a; x > 0; x -= x & -x) {
      ret += data[x];
    }
    return ret;
  }
};
bool compare(pair<int, int> left, pair<int, int> right) {
  if(left.second != right.second) return left.second < right.second;
  return left.first < right.first;
}
int compute(vector<pair<int, int>> &interval) {
  // for(auto it : interval) {
  //   cerr << "(" << it.first << "," << it.second << ")" << endl;
  // }
  sort(interval.begin(), interval.end(), compare);
  map<int, int> cmp;
  for(auto it : interval) {
    int v;
    v = it.first;
    if(!cmp.count(v)) cmp.insert(make_pair(v, cmp.size()));
    v = it.second;
    if(!cmp.count(v)) cmp.insert(make_pair(v, cmp.size()));
    v = it.first + 2*W + 2*D;
    if(!cmp.count(v)) cmp.insert(make_pair(v, cmp.size()));
    v = it.second + 2*W + 2*D;
    if(!cmp.count(v)) cmp.insert(make_pair(v, cmp.size()));
  }
  {
    int n = 0;
    for(auto &it : cmp) {
      it.second = n++;
    }
  }
  int c = 0;
  BIT bit(cmp.size());
  REP(i,N) {
    if(bit.sum(cmp[interval[i].second] + 1) - bit.sum(cmp[interval[i].first]) == 0) {
      ++c;
      bit.add(cmp[interval[i].second], 1);
      bit.add(cmp[interval[i].second + 2*W + 2*D], 1);
    }
  }
  return c;
}
signed main() {
  cin >> N >> W >> D;
  X.resize(N); Y.resize(N); F.resize(N);
  REP(i,N) {
    cin >> X[i] >> Y[i] >> F[i];
    Y[i] = D - Y[i];
  }
  auto interval = getInterval();
  // for(auto it : interval) {
  //   cerr << "(" << it.first << "," << it.second << ")" << endl;
  // }
  int ans = INF;
  REP(i,N) {
    vector<pair<int, int>> interval2;
    int offset = interval[i].first;
    REP(j,N) {
      int left = interval[(i + j)%N].first - offset;
      int right = interval[(i + j)%N].second - offset;
      if(left < 0) left += 2*W + 2*D;
      if(right < 0) right += 2*W + 2*D;
      if(right < left) right += 2*W + 2*D;
      interval2.emplace_back(left, right);
    }
    ans = min(ans, compute(interval2));
  }
  cout << ans << endl;
}