#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cstring>
#include <climits>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <vector>
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef pair<double, int> d_i;
typedef pair<ll, ll> ll_ll;
typedef pair<double, double> d_d;
struct edge { int u, v; ll w; int i; bool used; };
 
int MOD = 1000000007;

struct xyz {
	int x, y, z; bool f;
	xyz(int _x, int _y, int _z)
		: x(_x), y(_y), z(_z), f(true) {}
};

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

int main() {
	int n, x0, y0, t;
	cin >> n >> x0 >> y0 >> t;
	x0++; y0++;
	x0 *= 2; y0 *= 2;
	vector< vector<bool> > a(200, vector<bool>(200));
	while (n--) {
		int xs, ys, xe, ye;
		cin >> xs >> ys >> xe >> ye;
		xs++; ys++; xe++; ye++;
		xs *= 2; ys *= 2; xe *= 2; ye *= 2;
		if (xs == xe) {
			if (ys > ye) swap(ys, ye);
			for (int y = ys; y <= ye; y++)
				a[xs][y] = true;
		}
		else {
			if (xs > xe) swap(xs, xe);
			for (int x = xs; x <= xe; x++)
				a[x][ys] = true;
		}
	}
	queue<xyz> q;
	for (int z = 0; z < 4; z++)
		if (a[x0 + dx[z]][y0 + dy[z]])
			q.push(xyz(x0, y0, z));
	/*for (int i = 0; i < 53; i++) {
		for (int j = 0; j < 53; j++)
			cout << (a[i][j] ? ' ' : '#');
		cout << endl;
	}*/
	set<i_i> s;
	while (t--) {
		int d; cin >> d;
		d *= 2;
		while (d--) {
			vector< vector< vector<bool> > > b(200, vector< vector<bool> >(200, vector<bool>(4)));
			queue<xyz> _q;
			while (!q.empty()) {
				xyz e = q.front(); q.pop();
				for (int z = 0; z < 4; z++) {
					if (abs(z - e.z) != 2 && a[e.x + dx[z]][e.y + dy[z]]) {
						if (!e.f && abs(z - e.z) % 2) continue;
						if (!b[e.x + dx[z]][e.y + dy[z]][z]) {
							_q.push(xyz(e.x + dx[z], e.y + dy[z], z));
							b[e.x + dx[z]][e.y + dy[z]][z] = true;
						}
					}
				}
			}
			q = _q;
		}
		string c; cin >> c;
		int z;
		if (c == "W") z = 0;
		if (c == "S") z = 1;
		if (c == "E") z = 2;
		if (c == "N") z = 3;
		queue<xyz> _q;
		s.clear();
		while (!q.empty()) {
			xyz e = q.front(); q.pop();
			if ((e.z + 1) % 4 == z && a[e.x + dx[z]][e.y + dy[z]]) {
				e.f = false;
				e.z = z;
				_q.push(e);
				s.insert(i_i(e.x, e.y));
			}
			else if ((e.z + 3) % 4 == z && a[e.x + dx[z]][e.y + dy[z]]) {
				e.f = false;
				e.z = z;
				_q.push(e);
				s.insert(i_i(e.x, e.y));
			}
			else if (e.z == z) {
				_q.push(e);
				s.insert(i_i(e.x, e.y));
			}
		}
		q = _q;
		/*for (set<i_i>::iterator it = s.begin(); it != s.end(); it++)
			cout << it->first / 2 - 1 << ' ' << it->second / 2 - 1 << endl;
		cout << endl;*/
	}
	for (set<i_i>::iterator it = s.begin(); it != s.end(); it++)
		cout << it->first / 2 - 1 << ' ' << it->second / 2 - 1 << endl;
} 
### Prompt

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

Example

Input

4 2 1 1
1 1 1 2
2 2 2 1
2 2 1 2
1 1 2 1
9 N


Output

1 1
2 2

### Response

```cpp
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cstring>
#include <climits>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <vector>
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef pair<double, int> d_i;
typedef pair<ll, ll> ll_ll;
typedef pair<double, double> d_d;
struct edge { int u, v; ll w; int i; bool used; };
 
int MOD = 1000000007;

struct xyz {
	int x, y, z; bool f;
	xyz(int _x, int _y, int _z)
		: x(_x), y(_y), z(_z), f(true) {}
};

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

int main() {
	int n, x0, y0, t;
	cin >> n >> x0 >> y0 >> t;
	x0++; y0++;
	x0 *= 2; y0 *= 2;
	vector< vector<bool> > a(200, vector<bool>(200));
	while (n--) {
		int xs, ys, xe, ye;
		cin >> xs >> ys >> xe >> ye;
		xs++; ys++; xe++; ye++;
		xs *= 2; ys *= 2; xe *= 2; ye *= 2;
		if (xs == xe) {
			if (ys > ye) swap(ys, ye);
			for (int y = ys; y <= ye; y++)
				a[xs][y] = true;
		}
		else {
			if (xs > xe) swap(xs, xe);
			for (int x = xs; x <= xe; x++)
				a[x][ys] = true;
		}
	}
	queue<xyz> q;
	for (int z = 0; z < 4; z++)
		if (a[x0 + dx[z]][y0 + dy[z]])
			q.push(xyz(x0, y0, z));
	/*for (int i = 0; i < 53; i++) {
		for (int j = 0; j < 53; j++)
			cout << (a[i][j] ? ' ' : '#');
		cout << endl;
	}*/
	set<i_i> s;
	while (t--) {
		int d; cin >> d;
		d *= 2;
		while (d--) {
			vector< vector< vector<bool> > > b(200, vector< vector<bool> >(200, vector<bool>(4)));
			queue<xyz> _q;
			while (!q.empty()) {
				xyz e = q.front(); q.pop();
				for (int z = 0; z < 4; z++) {
					if (abs(z - e.z) != 2 && a[e.x + dx[z]][e.y + dy[z]]) {
						if (!e.f && abs(z - e.z) % 2) continue;
						if (!b[e.x + dx[z]][e.y + dy[z]][z]) {
							_q.push(xyz(e.x + dx[z], e.y + dy[z], z));
							b[e.x + dx[z]][e.y + dy[z]][z] = true;
						}
					}
				}
			}
			q = _q;
		}
		string c; cin >> c;
		int z;
		if (c == "W") z = 0;
		if (c == "S") z = 1;
		if (c == "E") z = 2;
		if (c == "N") z = 3;
		queue<xyz> _q;
		s.clear();
		while (!q.empty()) {
			xyz e = q.front(); q.pop();
			if ((e.z + 1) % 4 == z && a[e.x + dx[z]][e.y + dy[z]]) {
				e.f = false;
				e.z = z;
				_q.push(e);
				s.insert(i_i(e.x, e.y));
			}
			else if ((e.z + 3) % 4 == z && a[e.x + dx[z]][e.y + dy[z]]) {
				e.f = false;
				e.z = z;
				_q.push(e);
				s.insert(i_i(e.x, e.y));
			}
			else if (e.z == z) {
				_q.push(e);
				s.insert(i_i(e.x, e.y));
			}
		}
		q = _q;
		/*for (set<i_i>::iterator it = s.begin(); it != s.end(); it++)
			cout << it->first / 2 - 1 << ' ' << it->second / 2 - 1 << endl;
		cout << endl;*/
	}
	for (set<i_i>::iterator it = s.begin(); it != s.end(); it++)
		cout << it->first / 2 - 1 << ' ' << it->second / 2 - 1 << endl;
} 
```