#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class T>
using Table = vector<vector<T>>;
const ld eps=1e-9;

//// < "D:\D_Download\Visual Studio 2015\Projects\programing_contest_c++\Debug\a.txt"

struct status {
	int nx;
	int ny;
	int way;
	
};
bool operator<(const status&b, const status&a) {
	return b.nx * 100 + b.ny * 10000 + b.way < a.nx * 100 + a.ny * 10000 + a.way;
}

const int dx[4] = { -1,0,1,0 };
const int dy[4] = { 0,1,0,-1 };
int main() {
	int N, X0, Y0, T; cin >> N >> X0 >> Y0 >> T;
	vector<vector<vector<int>>>lines(60, vector < vector<int>>(60, vector<int>(4)));
	for (int i = 0; i < N; ++i) {
		int xs, ys, xe, ye; cin >> xs >> ys >> xe >> ye;
		if (xs > xe)swap(xs, xe);
		if (ys > ye)swap(ys, ye);
		if (xs == xe) {
			for (int y = ys; y < ye; ++y) {
				lines[y][xs][1] = true;
				lines[y + 1][xs][3] = true;
			}
		}
		else {
			for (int x = xs; x < xe; ++x) {
				lines[ys][x][2] = true;
				lines[ys][x + 1][0] = true;
			}
		}
	}
	vector<int>tways(1001,-1);
	map<char, int>mp;
	mp[N] = 3;
	mp['W'] = 0;
	mp['S'] = 3;
	mp['E'] = 2;
	mp['N'] = 1;
	int nt = 0;
	for (int i = 0; i < T; ++i) {
		int a;char b; cin >> a >> b;
		nt += a;
		tways[nt-1] = mp[b];
	}
	set<status>aset;
	for (int way = 0; way < 4; ++way) {
		if (lines[Y0][X0][way]) {
			aset.emplace(status{ X0,Y0,way });
		}
	}
	for (int t = 0; t < nt; ++t) {
		set<status>newset;
		for (auto sta : aset) {
			const int nowx = sta.nx;
			const int nowy = sta.ny;
			const int nowway = sta.way;
			const int nexx = nowx + dx[nowway];
			const int nexy = nowy + dy[nowway];
			for (int way = 0; way < 4; ++way) {
				if (tways[t] != -1) {
					if (nowway != tways[t] && way != tways[t])continue;
				}
				if ((nowway + 4 - way) % 4 == 2)continue;
				else if (lines[nexy][nexx][way]) {
					newset.emplace(status{ nexx,nexy,way });
				}
			}
		}
		aset = newset;
	}
	set<pair<int, int>>ansset;
	for (auto sta : aset) {
		ansset.emplace(sta.nx, sta.ny);
	}
	for (auto sta : ansset) {
		cout << sta.first << " " << sta.second << endl;
	}
	return 0;
}
### Prompt

Your task is to create a Cpp solution to the following problem:

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 "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class T>
using Table = vector<vector<T>>;
const ld eps=1e-9;

//// < "D:\D_Download\Visual Studio 2015\Projects\programing_contest_c++\Debug\a.txt"

struct status {
	int nx;
	int ny;
	int way;
	
};
bool operator<(const status&b, const status&a) {
	return b.nx * 100 + b.ny * 10000 + b.way < a.nx * 100 + a.ny * 10000 + a.way;
}

const int dx[4] = { -1,0,1,0 };
const int dy[4] = { 0,1,0,-1 };
int main() {
	int N, X0, Y0, T; cin >> N >> X0 >> Y0 >> T;
	vector<vector<vector<int>>>lines(60, vector < vector<int>>(60, vector<int>(4)));
	for (int i = 0; i < N; ++i) {
		int xs, ys, xe, ye; cin >> xs >> ys >> xe >> ye;
		if (xs > xe)swap(xs, xe);
		if (ys > ye)swap(ys, ye);
		if (xs == xe) {
			for (int y = ys; y < ye; ++y) {
				lines[y][xs][1] = true;
				lines[y + 1][xs][3] = true;
			}
		}
		else {
			for (int x = xs; x < xe; ++x) {
				lines[ys][x][2] = true;
				lines[ys][x + 1][0] = true;
			}
		}
	}
	vector<int>tways(1001,-1);
	map<char, int>mp;
	mp[N] = 3;
	mp['W'] = 0;
	mp['S'] = 3;
	mp['E'] = 2;
	mp['N'] = 1;
	int nt = 0;
	for (int i = 0; i < T; ++i) {
		int a;char b; cin >> a >> b;
		nt += a;
		tways[nt-1] = mp[b];
	}
	set<status>aset;
	for (int way = 0; way < 4; ++way) {
		if (lines[Y0][X0][way]) {
			aset.emplace(status{ X0,Y0,way });
		}
	}
	for (int t = 0; t < nt; ++t) {
		set<status>newset;
		for (auto sta : aset) {
			const int nowx = sta.nx;
			const int nowy = sta.ny;
			const int nowway = sta.way;
			const int nexx = nowx + dx[nowway];
			const int nexy = nowy + dy[nowway];
			for (int way = 0; way < 4; ++way) {
				if (tways[t] != -1) {
					if (nowway != tways[t] && way != tways[t])continue;
				}
				if ((nowway + 4 - way) % 4 == 2)continue;
				else if (lines[nexy][nexx][way]) {
					newset.emplace(status{ nexx,nexy,way });
				}
			}
		}
		aset = newset;
	}
	set<pair<int, int>>ansset;
	for (auto sta : aset) {
		ansset.emplace(sta.nx, sta.ny);
	}
	for (auto sta : ansset) {
		cout << sta.first << " " << sta.second << endl;
	}
	return 0;
}
```