#include <bits/stdc++.h>

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}

using namespace std;

int n,w,d;
int s[1010],g[1010];

inline int convert(int x,int y){
	if(x==0) return y;
	if(y==d) return d+x;
	if(x==w) return d+w+(d-y);
	if(y==0) return d+w+d+(w-x);
	return 0;
}

int greedy(int n,int start,int all){
	using state=tuple<int,int>;
	vector<state> ary;
	
	rep(i,n){
		bool add=true;

		if(s[i]<=g[i]){
			if(s[i]<=start && start <= g[i]) add=false;
		}else{
			if(start<=g[i]||s[i]<=start) add=false;
		}

		if(add){
			int cs=(s[i]-start+2*all)%all,cg=(g[i]-start+2*all)%all;
			ary.push_back(make_tuple(cg,cs));
		}
	}

	
	sort(_all(ary));	
	int res=1,cur=0;
	
	for(auto &it:ary){
		if(cur<get<1>(it)) 
			cur=get<0>(it),res++;
	}

	return res;
}

int main(void){
	cin >> n >> w >> d;
	rep(i,n){
		int x,y;
		char type;
		cin >> x >> y >> type;

		const int u=d-y,b=y,l=x,r=w-x;

		switch(type){
			case 'N':
				s[i]=(l<=u?convert(0,y+l):convert(x-u,d));
				g[i]=(r<=u?convert(w,y+r):convert(x+u,d));
				break;

			case 'W':
				s[i]=(b<=l?convert(x-b,0):convert(0,y-l));
				g[i]=(u<=l?convert(x-u,d):convert(0,y+l));
				break;

			case 'E':
				s[i]=(u<=r?convert(x+u,d):convert(w,y+r));
				g[i]=(b<=r?convert(x+b,0):convert(w,y-r));
				break;

			case 'S':
				s[i]=(r<=b?convert(w,y-r):convert(x+b,0));
				g[i]=(l<=b?convert(0,y-l):convert(x-b,0));
				break;
		}
	}

	const int all=2*(w+d);

	int ans=n;

	rep(i,n){
		chmin(ans,greedy(n,s[i],all));
		chmin(ans,greedy(n,g[i],all));
	}

	cout << ans << endl;
	return 0;
}
### Prompt

Your challenge is to write 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>

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}

using namespace std;

int n,w,d;
int s[1010],g[1010];

inline int convert(int x,int y){
	if(x==0) return y;
	if(y==d) return d+x;
	if(x==w) return d+w+(d-y);
	if(y==0) return d+w+d+(w-x);
	return 0;
}

int greedy(int n,int start,int all){
	using state=tuple<int,int>;
	vector<state> ary;
	
	rep(i,n){
		bool add=true;

		if(s[i]<=g[i]){
			if(s[i]<=start && start <= g[i]) add=false;
		}else{
			if(start<=g[i]||s[i]<=start) add=false;
		}

		if(add){
			int cs=(s[i]-start+2*all)%all,cg=(g[i]-start+2*all)%all;
			ary.push_back(make_tuple(cg,cs));
		}
	}

	
	sort(_all(ary));	
	int res=1,cur=0;
	
	for(auto &it:ary){
		if(cur<get<1>(it)) 
			cur=get<0>(it),res++;
	}

	return res;
}

int main(void){
	cin >> n >> w >> d;
	rep(i,n){
		int x,y;
		char type;
		cin >> x >> y >> type;

		const int u=d-y,b=y,l=x,r=w-x;

		switch(type){
			case 'N':
				s[i]=(l<=u?convert(0,y+l):convert(x-u,d));
				g[i]=(r<=u?convert(w,y+r):convert(x+u,d));
				break;

			case 'W':
				s[i]=(b<=l?convert(x-b,0):convert(0,y-l));
				g[i]=(u<=l?convert(x-u,d):convert(0,y+l));
				break;

			case 'E':
				s[i]=(u<=r?convert(x+u,d):convert(w,y+r));
				g[i]=(b<=r?convert(x+b,0):convert(w,y-r));
				break;

			case 'S':
				s[i]=(r<=b?convert(w,y-r):convert(x+b,0));
				g[i]=(l<=b?convert(0,y-l):convert(x-b,0));
				break;
		}
	}

	const int all=2*(w+d);

	int ans=n;

	rep(i,n){
		chmin(ans,greedy(n,s[i],all));
		chmin(ans,greedy(n,g[i],all));
	}

	cout << ans << endl;
	return 0;
}
```