#include<bits/stdc++.h>

using namespace std;

const int INF = 1 << 30;

int main()
{
  int N, W, D;
  cin >> N >> W >> D;

  int L = D + D + W + W;
  deque< pair< int, int > > range;
  for(int i = 0; i < N; i++) {
    int X, Y;
    char F;
    cin >> X >> Y >> F;
    if(F == 'N') range.emplace_back(X + Y, D + X + D - Y);
    if(F == 'E') range.emplace_back(D + X + D - Y, L - X - Y);
    if(F == 'S') range.emplace_back(L - X - Y, L - X + Y);
    if(F == 'W') range.emplace_back(L - X + Y, X + Y + L);
  }


  int ret = INF;
  for(int i = 0; i < N; i++) {

    sort(begin(range), end(range), [&](pair< int, int > a, pair< int, int > b)
    {
      swap(a.first, a.second);
      swap(b.first, b.second);
      return (a < b);
    });

    int count = 0;
    for(int j = 0; j < N;) {
      int ps = range[j].second;
      while(j < N && range[j].first <= ps) ++j;
      ++count;
    }
    ret = min(ret, count);
    range.front().first += L;
    range.front().second += L;
    range.push_back(range.front());
    range.pop_front();
  }
  cout << ret << endl;

}
### Prompt

Please provide a cpp coded solution to the problem described below:

Example

Input

2 10 6
4 4 E
6 4 W


Output

2

### Response

```cpp
#include<bits/stdc++.h>

using namespace std;

const int INF = 1 << 30;

int main()
{
  int N, W, D;
  cin >> N >> W >> D;

  int L = D + D + W + W;
  deque< pair< int, int > > range;
  for(int i = 0; i < N; i++) {
    int X, Y;
    char F;
    cin >> X >> Y >> F;
    if(F == 'N') range.emplace_back(X + Y, D + X + D - Y);
    if(F == 'E') range.emplace_back(D + X + D - Y, L - X - Y);
    if(F == 'S') range.emplace_back(L - X - Y, L - X + Y);
    if(F == 'W') range.emplace_back(L - X + Y, X + Y + L);
  }


  int ret = INF;
  for(int i = 0; i < N; i++) {

    sort(begin(range), end(range), [&](pair< int, int > a, pair< int, int > b)
    {
      swap(a.first, a.second);
      swap(b.first, b.second);
      return (a < b);
    });

    int count = 0;
    for(int j = 0; j < N;) {
      int ps = range[j].second;
      while(j < N && range[j].first <= ps) ++j;
      ++count;
    }
    ret = min(ret, count);
    range.front().first += L;
    range.front().second += L;
    range.push_back(range.front());
    range.pop_front();
  }
  cout << ret << endl;

}
```