#include<bits/stdc++.h>
using namespace std;

int N, W, D;
vector<pair<int, int> > interval;

int projection(int x, int y, int dx, int dy){
	int dist = 1000000000;
	int xx = x;
	int yy = y;
	if(dx > 0) dist = min(dist, W - x);
	if(dx < 0) dist = min(dist, x);
	if(dy > 0) dist = min(dist, D - y);
	if(dy < 0) dist = min(dist, y);
	x += dist * dx;
	y += dist * dy;
	int ret;
	if(x == 0) ret =  y;
	else if(y == D) ret = D + x;
	else if(x == W) ret =  D + W + (D - y);
	else ret =  D + W + D + (W - x);
	return ret;
}



int main(){
	cin >> N >> W >> D;
	for(int i = 0; i < N; i++){
		int x, y; char c;
		cin >> x >> y >> c;
		int s, e;
		if(c == 'N'){
			s = projection(x, y, -1, 1);
			e = projection(x, y, 1, 1);
		}else if(c == 'E'){
			s = projection(x, y,  1, 1);
			e = projection(x, y, 1, -1);
		}else if(c == 'S'){
			s = projection(x, y, 1, -1);
			e = projection(x, y, -1, -1);
		}else if(c == 'W'){
			s = projection(x, y, -1, -1);
			e = projection(x, y, -1, 1);
		}
		if(s > e) e += 2 * W + 2 * D;
		interval.push_back({e, s});
	}
	sort(interval.begin(), interval.end());

	int ans = 10000000;
	for(int i = 0; i < N; i++){
		int a1 = 1;
		int start = interval[i].first;
		int cur = start;
		//cout << "=======" << i << "===========" << endl;
		for(int j = 1; j < N; j++){
			int e = interval[i + j].first;
			int s = interval[i + j].second;
		//	printf("%d+%d (%d, %d) %d %d\n", i, j, s, e, cur, start);
			if(!(s <= cur && cur <= e)  && start + 2 * W + 2 * D > e ){
				a1 += 1;
				cur = e;
			}
		}
		//cout << "(" << a1 << ")" << endl;
		ans = min(ans, a1);
		int e = interval[i].first + 2 * W + 2 * D;
		int s = interval[i].second + 2 * W + 2 * D;
		interval.push_back({e, s});
	}
	cout << ans << endl;	
}
### Prompt

Please formulate 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;
vector<pair<int, int> > interval;

int projection(int x, int y, int dx, int dy){
	int dist = 1000000000;
	int xx = x;
	int yy = y;
	if(dx > 0) dist = min(dist, W - x);
	if(dx < 0) dist = min(dist, x);
	if(dy > 0) dist = min(dist, D - y);
	if(dy < 0) dist = min(dist, y);
	x += dist * dx;
	y += dist * dy;
	int ret;
	if(x == 0) ret =  y;
	else if(y == D) ret = D + x;
	else if(x == W) ret =  D + W + (D - y);
	else ret =  D + W + D + (W - x);
	return ret;
}



int main(){
	cin >> N >> W >> D;
	for(int i = 0; i < N; i++){
		int x, y; char c;
		cin >> x >> y >> c;
		int s, e;
		if(c == 'N'){
			s = projection(x, y, -1, 1);
			e = projection(x, y, 1, 1);
		}else if(c == 'E'){
			s = projection(x, y,  1, 1);
			e = projection(x, y, 1, -1);
		}else if(c == 'S'){
			s = projection(x, y, 1, -1);
			e = projection(x, y, -1, -1);
		}else if(c == 'W'){
			s = projection(x, y, -1, -1);
			e = projection(x, y, -1, 1);
		}
		if(s > e) e += 2 * W + 2 * D;
		interval.push_back({e, s});
	}
	sort(interval.begin(), interval.end());

	int ans = 10000000;
	for(int i = 0; i < N; i++){
		int a1 = 1;
		int start = interval[i].first;
		int cur = start;
		//cout << "=======" << i << "===========" << endl;
		for(int j = 1; j < N; j++){
			int e = interval[i + j].first;
			int s = interval[i + j].second;
		//	printf("%d+%d (%d, %d) %d %d\n", i, j, s, e, cur, start);
			if(!(s <= cur && cur <= e)  && start + 2 * W + 2 * D > e ){
				a1 += 1;
				cur = e;
			}
		}
		//cout << "(" << a1 << ")" << endl;
		ans = min(ans, a1);
		int e = interval[i].first + 2 * W + 2 * D;
		int s = interval[i].second + 2 * W + 2 * D;
		interval.push_back({e, s});
	}
	cout << ans << endl;	
}
```