#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n,w,d,mod;
vector<pair<int,int> >a;
int main()
{
	cin>>n>>w>>d;
	mod=2*(w+d);
	for(int i=0;i<n;i++)
	{
		int x,y;char f;cin>>x>>y>>f;
		a.push_back(make_pair(
			(f=='E'?d+x+y:f=='W'?mod-x+d-y:f=='S'?d+x-y:mod-x-d+y)%mod,
			(f=='E'?mod-x-d+y:f=='W'?d+x-y:f=='S'?d+x+y:mod-x+d-y)%mod));
	}
	int ans=1e9;
	for(int i=0;i<n;i++)
	{
		int now=1,id=a[i].second;
		vector<pair<int,int> >m;
		for(int j=0;j<n;j++)
		{
			if(a[j].first<=id&&id<=a[j].second||a[j].second<a[j].first&&(id<=a[j].second||a[j].first<=id))continue;
			m.push_back(make_pair((a[j].second-id+mod)%mod,(a[j].first-id+mod)%mod));
		}
		sort(m.begin(),m.end());
		int p=-1;
		for(int j=0;j<m.size();j++)
		{
			if(p<m[j].second)
			{
				p=m[j].first;
				now++;
			}
		}
		ans=min(ans,now);
	}
	cout<<ans<<endl;
}

### Prompt

In CPP, your task is to solve the following problem:

Example

Input

2 10 6
4 4 E
6 4 W


Output

2

### Response

```cpp
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n,w,d,mod;
vector<pair<int,int> >a;
int main()
{
	cin>>n>>w>>d;
	mod=2*(w+d);
	for(int i=0;i<n;i++)
	{
		int x,y;char f;cin>>x>>y>>f;
		a.push_back(make_pair(
			(f=='E'?d+x+y:f=='W'?mod-x+d-y:f=='S'?d+x-y:mod-x-d+y)%mod,
			(f=='E'?mod-x-d+y:f=='W'?d+x-y:f=='S'?d+x+y:mod-x+d-y)%mod));
	}
	int ans=1e9;
	for(int i=0;i<n;i++)
	{
		int now=1,id=a[i].second;
		vector<pair<int,int> >m;
		for(int j=0;j<n;j++)
		{
			if(a[j].first<=id&&id<=a[j].second||a[j].second<a[j].first&&(id<=a[j].second||a[j].first<=id))continue;
			m.push_back(make_pair((a[j].second-id+mod)%mod,(a[j].first-id+mod)%mod));
		}
		sort(m.begin(),m.end());
		int p=-1;
		for(int j=0;j<m.size();j++)
		{
			if(p<m[j].second)
			{
				p=m[j].first;
				now++;
			}
		}
		ans=min(ans,now);
	}
	cout<<ans<<endl;
}

```