#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <queue>
using namespace std;

#define fi first
#define se second

typedef pair<int,int> pii;
const int INF = 1e9;

struct s {
	int ps,pp;
	int idx;
	s(){}
	s(int ps_, int pp_, int idx_) {
		ps = ps_; pp = pp_; idx = idx_;
	}
};

bool operator<(s a, s b) {
	return a.pp > b.pp;
}

int main() {
	int n, w, d;
	vector<pii> v;
	cin >> n >> w >> d;
	for(int i = 0; i < n; i++) {
		int x, y;
		char f;
		int nx, ny;
		cin >> x >> y >> f;
		switch(f) {
			case 'N':
				nx = w-x;
				ny = d-y;
				break;
			case 'W':
				nx = w + d-y;
				ny = x;
				break;
			case 'S':
				nx = w+d + x;
				ny = y;
				break;
			case 'E':
				nx = w+d+w + y;
				ny = w-x;
				break;
		}
		int ps, pp;
		ps = nx - ny;
		pp = nx + ny;
		v.push_back(pii(ps,pp));
	}

	sort(v.begin(), v.end());
	int res = 10000;
	for(int k = 0; k < 2; k++) {
	for(int i = 0; i < v.size(); i++) {
		vector<pii> vv;
		vector<int> pushed(n,0);

		vv.resize(v.size());
		for(int j = 0; j < v.size(); j++) {
			vv[j].fi = (v[(i+j)%n].fi - (k?v[i].se:v[i].fi) + 4*(w+d)) % (2*(w+d));
			vv[j].se = (v[(i+j)%n].se - (k?v[i].se:v[i].fi) + 4*(w+d)) % (2*(w+d));
			if(vv[j].fi > vv[j].se) vv[j].se += 2*(w+d);
		}
		sort(vv.begin(), vv.end());
		/*
		for(int j = 0; j < vv.size(); j++)
			cout << vv[j].fi << "," << vv[j].se << " " ;
		cout << endl;
		// */

		for(int j = 0; j < vv.size(); j++) {
			if(2*(w+d) <= vv[j].se || vv[j].fi == 0) {
				pushed[j] = 1;
			}
		}

		/*
		for(int i = 0; i < pushed.size(); i++)
			cout << pushed[i] << " ";
		cout << endl;
		// */

		priority_queue<s> pq;
		int tmp = 1;
		for(int j = 0; j < vv.size(); j++)  {
			if(!pushed[j]) {
				if(pq.empty() || vv[j].fi <= pq.top().pp) {
					pq.push(s(vv[j].fi,vv[j].se,j));
					pushed[j] = 1;
				}
				else {
					while(pq.size()) pq.pop();
					tmp++;
					pq.push(s(vv[j].fi,vv[j].se,j));
					pushed[j] = 1;
				}
			}
		}
		if(pq.size()) tmp++;
		res = min(res,tmp);

		/*
		for(int i = 0; i < pushed.size(); i++)
			cout << pushed[i] << " ";
		cout << endl;
		// */

	}
	}
	cout << res << endl;
}
### 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 <utility>
#include <algorithm>
#include <queue>
using namespace std;

#define fi first
#define se second

typedef pair<int,int> pii;
const int INF = 1e9;

struct s {
	int ps,pp;
	int idx;
	s(){}
	s(int ps_, int pp_, int idx_) {
		ps = ps_; pp = pp_; idx = idx_;
	}
};

bool operator<(s a, s b) {
	return a.pp > b.pp;
}

int main() {
	int n, w, d;
	vector<pii> v;
	cin >> n >> w >> d;
	for(int i = 0; i < n; i++) {
		int x, y;
		char f;
		int nx, ny;
		cin >> x >> y >> f;
		switch(f) {
			case 'N':
				nx = w-x;
				ny = d-y;
				break;
			case 'W':
				nx = w + d-y;
				ny = x;
				break;
			case 'S':
				nx = w+d + x;
				ny = y;
				break;
			case 'E':
				nx = w+d+w + y;
				ny = w-x;
				break;
		}
		int ps, pp;
		ps = nx - ny;
		pp = nx + ny;
		v.push_back(pii(ps,pp));
	}

	sort(v.begin(), v.end());
	int res = 10000;
	for(int k = 0; k < 2; k++) {
	for(int i = 0; i < v.size(); i++) {
		vector<pii> vv;
		vector<int> pushed(n,0);

		vv.resize(v.size());
		for(int j = 0; j < v.size(); j++) {
			vv[j].fi = (v[(i+j)%n].fi - (k?v[i].se:v[i].fi) + 4*(w+d)) % (2*(w+d));
			vv[j].se = (v[(i+j)%n].se - (k?v[i].se:v[i].fi) + 4*(w+d)) % (2*(w+d));
			if(vv[j].fi > vv[j].se) vv[j].se += 2*(w+d);
		}
		sort(vv.begin(), vv.end());
		/*
		for(int j = 0; j < vv.size(); j++)
			cout << vv[j].fi << "," << vv[j].se << " " ;
		cout << endl;
		// */

		for(int j = 0; j < vv.size(); j++) {
			if(2*(w+d) <= vv[j].se || vv[j].fi == 0) {
				pushed[j] = 1;
			}
		}

		/*
		for(int i = 0; i < pushed.size(); i++)
			cout << pushed[i] << " ";
		cout << endl;
		// */

		priority_queue<s> pq;
		int tmp = 1;
		for(int j = 0; j < vv.size(); j++)  {
			if(!pushed[j]) {
				if(pq.empty() || vv[j].fi <= pq.top().pp) {
					pq.push(s(vv[j].fi,vv[j].se,j));
					pushed[j] = 1;
				}
				else {
					while(pq.size()) pq.pop();
					tmp++;
					pq.push(s(vv[j].fi,vv[j].se,j));
					pushed[j] = 1;
				}
			}
		}
		if(pq.size()) tmp++;
		res = min(res,tmp);

		/*
		for(int i = 0; i < pushed.size(); i++)
			cout << pushed[i] << " ";
		cout << endl;
		// */

	}
	}
	cout << res << endl;
}
```