#include<bits/stdc++.h>
#define ms(x,y) memset(x,y,sizeof(x))
using namespace std;
int n,w,d,huan;
const int N=2005;
struct edge{
	int l,r;
}e[N];
int en;
bool cmp(const edge &A,const edge& B){
	return A.r<B.r;
}
bool exi[N];


bool in(int i,int pos){
	if(e[i].l<=e[i].r){
		if(pos>=e[i].l && pos<=e[i].r)return true;
	}
	else if(pos>=e[i].l || pos<=e[i].r)return true;
	return false;
}

int gao(int now,int pos){
	int ans=1;
	for(int i=0;i<en;i++)
		if(in(i,pos))exi[i]=false;
	for(int i=(now+1)%en,j;i!=now;) {
		if(exi[i]) {
			exi[i]=false;
			ans++;
			for(j=(i+1)%en;j!=now;j=(j+1)%en)
				if((!exi[j]) || in(j,e[i].r)) exi[j]=false;
				else break;
			i=j;
		}
		else i++;
	}
	return ans;
}


void add(int l,int r){
	if(l<0)l+=huan;
	if(r<0)r+=huan;
	if(l>=huan)l-=huan;
	if(r>=huan)r-=huan;
	e[en].l=l;
	e[en++].r=r;
}
		
int main(){
	cin>>n>>w>>d;
	huan=2*d+2*w;
	int x,y;
	char ch;
	en=0;
	for(int i=1;i<=n;i++){
		scanf("%d %d %c",&x,&y,&ch);
		if(ch=='W')
			add(y-x,y+x);
		else if (ch == 'N'){
			y=d-y;
			add(x-y+d,x+y+d);
		}
		else if(ch == 'E'){
			x=w-x;y=d-y;
			add(d+w+y-x,d+w+y+x);
		}
		else if(ch == 'S'){
			x=w-x;
			add(d+w+d+x-y,d+w+d+x+y);
		}
	}
	sort(e,e+en,cmp);
	int ans=1000000;
	for(int i=0;i<en;i++){
		ms(exi,1);
		ans=min(ans,gao(i,e[i].l));
		ms(exi,1);
		ans=min(ans,gao(i,e[i].r));
	}
	cout<<ans<<endl;
	return 0;
}
### Prompt

Construct a CPP code solution to the problem outlined:

Example

Input

2 10 6
4 4 E
6 4 W


Output

2

### Response

```cpp
#include<bits/stdc++.h>
#define ms(x,y) memset(x,y,sizeof(x))
using namespace std;
int n,w,d,huan;
const int N=2005;
struct edge{
	int l,r;
}e[N];
int en;
bool cmp(const edge &A,const edge& B){
	return A.r<B.r;
}
bool exi[N];


bool in(int i,int pos){
	if(e[i].l<=e[i].r){
		if(pos>=e[i].l && pos<=e[i].r)return true;
	}
	else if(pos>=e[i].l || pos<=e[i].r)return true;
	return false;
}

int gao(int now,int pos){
	int ans=1;
	for(int i=0;i<en;i++)
		if(in(i,pos))exi[i]=false;
	for(int i=(now+1)%en,j;i!=now;) {
		if(exi[i]) {
			exi[i]=false;
			ans++;
			for(j=(i+1)%en;j!=now;j=(j+1)%en)
				if((!exi[j]) || in(j,e[i].r)) exi[j]=false;
				else break;
			i=j;
		}
		else i++;
	}
	return ans;
}


void add(int l,int r){
	if(l<0)l+=huan;
	if(r<0)r+=huan;
	if(l>=huan)l-=huan;
	if(r>=huan)r-=huan;
	e[en].l=l;
	e[en++].r=r;
}
		
int main(){
	cin>>n>>w>>d;
	huan=2*d+2*w;
	int x,y;
	char ch;
	en=0;
	for(int i=1;i<=n;i++){
		scanf("%d %d %c",&x,&y,&ch);
		if(ch=='W')
			add(y-x,y+x);
		else if (ch == 'N'){
			y=d-y;
			add(x-y+d,x+y+d);
		}
		else if(ch == 'E'){
			x=w-x;y=d-y;
			add(d+w+y-x,d+w+y+x);
		}
		else if(ch == 'S'){
			x=w-x;
			add(d+w+d+x-y,d+w+d+x+y);
		}
	}
	sort(e,e+en,cmp);
	int ans=1000000;
	for(int i=0;i<en;i++){
		ms(exi,1);
		ans=min(ans,gao(i,e[i].l));
		ms(exi,1);
		ans=min(ans,gao(i,e[i].r));
	}
	cout<<ans<<endl;
	return 0;
}
```