#include<bits/stdc++.h>
using namespace std;
int n,w,d,mod;
int sum[400040];
int check[2222];
vector<pair<int,int> >a;
int main(){
    cin>>n>>w>>d;
    mod=2*(d+w);
    for(int i=0;i<n;i++)
    {
        int x,y;char f;cin>>x>>y>>f;
        if(f=='E')
        {
            a.push_back(make_pair(d+x+y,(mod-x-d+y)%mod));
        }
        else if(f=='W')a.push_back(make_pair((mod-x+d-y)%mod,(mod+d+x-y)%mod));
        else if(f=='N')a.push_back(make_pair((mod-x-d+y)%mod,(mod-x+d-y)%mod));
        else a.push_back(make_pair(d+x-y,d+x+y));
        check[i*2]=a[i].first;
        check[i*2+1]=a[i].second;
    }
    int ans=1e9;
    for(int index=0;index<2*n;index++)
    {
        int id=check[index];
        vector<pair<int,int> >m;
        int now=1;
        for(int i=0;i<n;i++)
        {
            bool inc=0;
            if(a[i].first<=id&&id<=a[i].second)inc=1;
            else if(a[i].first>a[i].second&&(id<=a[i].second||id>=a[i].first))inc=1;
            if(!inc)
            {
                m.push_back(make_pair((a[i].second+mod-id)%mod,(a[i].first+mod-id)%mod));
            }
        }
        sort(m.begin(),m.end());
        int p=-114514;
        for(int i=0;i<m.size();i++)
        {
            if(m[i].second>p)
            {
                now++;
                p=m[i].first;
            }
        }
        ans=min(ans,now);
    }
    cout<<ans<<endl;
}


### Prompt

Your task is to create 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;
int n,w,d,mod;
int sum[400040];
int check[2222];
vector<pair<int,int> >a;
int main(){
    cin>>n>>w>>d;
    mod=2*(d+w);
    for(int i=0;i<n;i++)
    {
        int x,y;char f;cin>>x>>y>>f;
        if(f=='E')
        {
            a.push_back(make_pair(d+x+y,(mod-x-d+y)%mod));
        }
        else if(f=='W')a.push_back(make_pair((mod-x+d-y)%mod,(mod+d+x-y)%mod));
        else if(f=='N')a.push_back(make_pair((mod-x-d+y)%mod,(mod-x+d-y)%mod));
        else a.push_back(make_pair(d+x-y,d+x+y));
        check[i*2]=a[i].first;
        check[i*2+1]=a[i].second;
    }
    int ans=1e9;
    for(int index=0;index<2*n;index++)
    {
        int id=check[index];
        vector<pair<int,int> >m;
        int now=1;
        for(int i=0;i<n;i++)
        {
            bool inc=0;
            if(a[i].first<=id&&id<=a[i].second)inc=1;
            else if(a[i].first>a[i].second&&(id<=a[i].second||id>=a[i].first))inc=1;
            if(!inc)
            {
                m.push_back(make_pair((a[i].second+mod-id)%mod,(a[i].first+mod-id)%mod));
            }
        }
        sort(m.begin(),m.end());
        int p=-114514;
        for(int i=0;i<m.size();i++)
        {
            if(m[i].second>p)
            {
                now++;
                p=m[i].first;
            }
        }
        ans=min(ans,now);
    }
    cout<<ans<<endl;
}


```