#include <iostream>
#include <vector>
#include <algorithm>
#include <bitset>
#include <utility>
using namespace std;
const int inf = 1e9;
const int MAXN = 1000;

int upper_right(int x, int y, int w, int h){
	return 2*w +y -x;
}
int upper_left(int x, int y, int w, int h){
	return 2*w +2*h -x -y;
}
int lower_right(int x, int y, int w, int h){
	return x+y;
}
int lower_left(int x, int y, int w, int h){
	return x>y? x-y: 2*h +2*w +x-y;
}

int main(){
	int n,w,h;
	cin >> n >> w >> h;
	vector<int> s(n), e(n);
	for(int i=0; i<n; i++){
		int x,y;
		char f;
		cin >> x >> y >> f;
		if(f == 'N'){
			s[i] = upper_right(x, y, w, h);
			e[i] = upper_left(x, y, w, h);
		}
		if(f == 'W'){
			s[i] = upper_left(x, y, w, h);
			e[i] = lower_left(x, y, w, h);
		}
		if(f == 'S'){
			s[i] = lower_left(x, y, w, h);
			e[i] = lower_right(x, y, w, h);
		}
		if(f == 'E'){
			s[i] = lower_right(x, y, w, h);
			e[i] = upper_right(x, y, w, h);
		}
	}
	vector<pair<int ,int> > es(n);
	for(int i=0; i<n; i++) es[i] = make_pair(e[i], s[i]);
	sort(es.begin(), es.end());
	for(int i=0; i<n; i++){ s[i] = es[i].second; e[i] = es[i].first; }
	
	vector<bitset<MAXN> > cover(n);
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			if((i == j) ||
				(s[j] < e[j] && s[j]<=e[i] && e[i]<=e[j]) ||
				(s[j] > e[j] && (e[i]<=e[j] || s[j]<=e[i]))){
				cover[i][j] = 1;
			}
		}
	}
	
	int ans = inf;
	for(int i=0; i<n; i++){
		int sub = 0;
		bitset<MAXN> cov;
		for(int j=0; j<n; j++){
			if(cov[(i+j)%n] == 0){
				cov |= cover[(i+j)%n];
				sub++;
			}
		}
		ans = min(ans, sub);
	}
	cout << ans << endl;
	return 0;
}

### Prompt

Please provide a CPP coded solution to the problem described below:

Example

Input

2 10 6
4 4 E
6 4 W


Output

2

### Response

```cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <bitset>
#include <utility>
using namespace std;
const int inf = 1e9;
const int MAXN = 1000;

int upper_right(int x, int y, int w, int h){
	return 2*w +y -x;
}
int upper_left(int x, int y, int w, int h){
	return 2*w +2*h -x -y;
}
int lower_right(int x, int y, int w, int h){
	return x+y;
}
int lower_left(int x, int y, int w, int h){
	return x>y? x-y: 2*h +2*w +x-y;
}

int main(){
	int n,w,h;
	cin >> n >> w >> h;
	vector<int> s(n), e(n);
	for(int i=0; i<n; i++){
		int x,y;
		char f;
		cin >> x >> y >> f;
		if(f == 'N'){
			s[i] = upper_right(x, y, w, h);
			e[i] = upper_left(x, y, w, h);
		}
		if(f == 'W'){
			s[i] = upper_left(x, y, w, h);
			e[i] = lower_left(x, y, w, h);
		}
		if(f == 'S'){
			s[i] = lower_left(x, y, w, h);
			e[i] = lower_right(x, y, w, h);
		}
		if(f == 'E'){
			s[i] = lower_right(x, y, w, h);
			e[i] = upper_right(x, y, w, h);
		}
	}
	vector<pair<int ,int> > es(n);
	for(int i=0; i<n; i++) es[i] = make_pair(e[i], s[i]);
	sort(es.begin(), es.end());
	for(int i=0; i<n; i++){ s[i] = es[i].second; e[i] = es[i].first; }
	
	vector<bitset<MAXN> > cover(n);
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			if((i == j) ||
				(s[j] < e[j] && s[j]<=e[i] && e[i]<=e[j]) ||
				(s[j] > e[j] && (e[i]<=e[j] || s[j]<=e[i]))){
				cover[i][j] = 1;
			}
		}
	}
	
	int ans = inf;
	for(int i=0; i<n; i++){
		int sub = 0;
		bitset<MAXN> cov;
		for(int j=0; j<n; j++){
			if(cov[(i+j)%n] == 0){
				cov |= cover[(i+j)%n];
				sub++;
			}
		}
		ans = min(ans, sub);
	}
	cout << ans << endl;
	return 0;
}

```