#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <cassert>
#include <map>
using namespace std;

int dx[4] = { 1, 0, -1, 0 }, dy[4] = { 0, 1, 0, -1 };
char h[4] = { 'E', 'N', 'W', 'S' };
int G[51][51][4];
int dir[1100];
int dp[1100][51][51][4];

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	int n, x0, y0, t;
	while(cin >> n >> x0 >> y0 >> t) {
		memset(dir, -1, sizeof dir);
		memset(G, 0, sizeof G);
		memset(dp, 0, sizeof dp);
		for(int i = 0; i < n; i++) {
			int x1, y1, x2, y2;
			cin >> x1 >> y1 >> x2 >> y2;
			if(x1 > x2) swap(x1, x2);
			if(y1 > y2) swap(y1, y2);
			if(x1 == x2) {
				for(int y = y1; y < y2; y++) {
					G[x1][y][1] = 1;
					G[x1][y + 1][3] = 1;
				}
			}
			else {
				for(int x = x1; x < x2; x++) {
					G[x][y1][0] = 1;
					G[x + 1][y1][2] = 1;
				}
			}
		}

		int dsum = 0;
		for(int i = 0; i < t; i++) {
			int d;
			char c;
			cin >> d >> c;
			dsum += d;
			int x = find(h, h + 4, c) - h;
			dir[dsum] = x;
		}

		for(int k = 0; k < 4; k++) {
			dp[0][x0][y0][k] = 1;
		}

		for(int i = 0; i <= dsum; i++) {
			for(int x = 0; x <= 50; x++) {
				for(int y = 0; y <= 50; y++) {
					for(int k = 0; k < 4; k++) {
						if(!dp[i][x][y][k]) continue;
						bool ok = 0;
						for(int l = 0; l < 4; l++) {
							if(abs(k - l) == 2) continue;
							if(!G[x][y][l]) continue;
							if(dir[i] != -1 && dir[i] != k && dir[i] != l) {
								continue;
							}
							int nx = x + dx[l], ny = y + dy[l];
							dp[i + 1][nx][ny][l] = 1;
							ok = 1;
						}
						dp[i][x][y][k] = ok;
					}
				}
			}

		}
		for(int x = 0; x <= 50; x++) {
			for(int y = 0; y <= 50; y++) {
				for(int k = 0; k < 4; k++) {
					if(dp[dsum][x][y][k]) {
						cout << x << " " << y << "\n";
						break;
					}
				}
			}
		}
		//cout << endl;
	}
}
### Prompt

Please create a solution in cpp 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 <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <cassert>
#include <map>
using namespace std;

int dx[4] = { 1, 0, -1, 0 }, dy[4] = { 0, 1, 0, -1 };
char h[4] = { 'E', 'N', 'W', 'S' };
int G[51][51][4];
int dir[1100];
int dp[1100][51][51][4];

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	int n, x0, y0, t;
	while(cin >> n >> x0 >> y0 >> t) {
		memset(dir, -1, sizeof dir);
		memset(G, 0, sizeof G);
		memset(dp, 0, sizeof dp);
		for(int i = 0; i < n; i++) {
			int x1, y1, x2, y2;
			cin >> x1 >> y1 >> x2 >> y2;
			if(x1 > x2) swap(x1, x2);
			if(y1 > y2) swap(y1, y2);
			if(x1 == x2) {
				for(int y = y1; y < y2; y++) {
					G[x1][y][1] = 1;
					G[x1][y + 1][3] = 1;
				}
			}
			else {
				for(int x = x1; x < x2; x++) {
					G[x][y1][0] = 1;
					G[x + 1][y1][2] = 1;
				}
			}
		}

		int dsum = 0;
		for(int i = 0; i < t; i++) {
			int d;
			char c;
			cin >> d >> c;
			dsum += d;
			int x = find(h, h + 4, c) - h;
			dir[dsum] = x;
		}

		for(int k = 0; k < 4; k++) {
			dp[0][x0][y0][k] = 1;
		}

		for(int i = 0; i <= dsum; i++) {
			for(int x = 0; x <= 50; x++) {
				for(int y = 0; y <= 50; y++) {
					for(int k = 0; k < 4; k++) {
						if(!dp[i][x][y][k]) continue;
						bool ok = 0;
						for(int l = 0; l < 4; l++) {
							if(abs(k - l) == 2) continue;
							if(!G[x][y][l]) continue;
							if(dir[i] != -1 && dir[i] != k && dir[i] != l) {
								continue;
							}
							int nx = x + dx[l], ny = y + dy[l];
							dp[i + 1][nx][ny][l] = 1;
							ok = 1;
						}
						dp[i][x][y][k] = ok;
					}
				}
			}

		}
		for(int x = 0; x <= 50; x++) {
			for(int y = 0; y <= 50; y++) {
				for(int k = 0; k < 4; k++) {
					if(dp[dsum][x][y][k]) {
						cout << x << " " << y << "\n";
						break;
					}
				}
			}
		}
		//cout << endl;
	}
}
```