#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// const long double PI = acos(-1);
constexpr int inf = 1e9;
constexpr ll INF = 2e18;
// constexpr ll MOD = 1e9+7;
constexpr ll MOD = 998244353;

int n,w,d;
vector<pair<ll,ll>> v;

void solve();

void input() {
    cin >> n >> w >> d;
    for (int i = 0; i < n; i++) {
        ll x,y;
        char f;
        cin >> x >> y >> f;
        ll left,right,mid;
        switch(f) {
            case 'E':
                mid = w + d - y;
                left = mid - w + x;
                right = mid + w - x;
                break;
            case 'S':
                mid = w * 2 + d - x;
                left = mid - y;
                right = mid + y;
                break;
            case 'W':
                mid = w * 2 + d + y;
                left = mid - x;
                right = mid + x;
                break;
            case 'N':
                mid = x;
                left = mid - d + y;
                right = mid + d - y;
                break;
        }
        if (right > 2 * (w + d)) {
            left -= 2 * (w + d);
            right -= 2 * (w + d);
        }
        v.push_back({right,left});
        v.push_back({right + 2 * (w + d), left + 2 * (w + d)});
    }
    sort(v.begin(),v.end());
    solve();

}

void solve() {
    // for (int i = 0; i < v.size(); i++) {
    //     cout << v[i].first << " " << v[i].second << endl;
    // }
    int ans = n;
    for (int i = 0; i < n; i++) {
        int cnt = 1;
        int right = v[i].first;
        for (int j = 1; j < n; j++) {
            if (v[i + j].second > right) {
                cnt++;
                right = v[i + j].first;
            }
        }
        ans = min(ans, cnt);
    }
    cout << ans << endl;
}

int main(int argc, char *argv[]) {
    input();
    return 0;
}


### Prompt

Please formulate a CPP solution to the following problem:

Example

Input

2 10 6
4 4 E
6 4 W


Output

2

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// const long double PI = acos(-1);
constexpr int inf = 1e9;
constexpr ll INF = 2e18;
// constexpr ll MOD = 1e9+7;
constexpr ll MOD = 998244353;

int n,w,d;
vector<pair<ll,ll>> v;

void solve();

void input() {
    cin >> n >> w >> d;
    for (int i = 0; i < n; i++) {
        ll x,y;
        char f;
        cin >> x >> y >> f;
        ll left,right,mid;
        switch(f) {
            case 'E':
                mid = w + d - y;
                left = mid - w + x;
                right = mid + w - x;
                break;
            case 'S':
                mid = w * 2 + d - x;
                left = mid - y;
                right = mid + y;
                break;
            case 'W':
                mid = w * 2 + d + y;
                left = mid - x;
                right = mid + x;
                break;
            case 'N':
                mid = x;
                left = mid - d + y;
                right = mid + d - y;
                break;
        }
        if (right > 2 * (w + d)) {
            left -= 2 * (w + d);
            right -= 2 * (w + d);
        }
        v.push_back({right,left});
        v.push_back({right + 2 * (w + d), left + 2 * (w + d)});
    }
    sort(v.begin(),v.end());
    solve();

}

void solve() {
    // for (int i = 0; i < v.size(); i++) {
    //     cout << v[i].first << " " << v[i].second << endl;
    // }
    int ans = n;
    for (int i = 0; i < n; i++) {
        int cnt = 1;
        int right = v[i].first;
        for (int j = 1; j < n; j++) {
            if (v[i + j].second > right) {
                cnt++;
                right = v[i + j].first;
            }
        }
        ans = min(ans, cnt);
    }
    cout << ans << endl;
}

int main(int argc, char *argv[]) {
    input();
    return 0;
}


```