#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;


inline int toidx(int x, int y, int d, int outnode)
{
	return (x * 51 + y) * 8 + d * 2 + outnode;
}

inline int todir(int idx)
{
	return (idx / 2) % 4;
}


int main()
{
	int n, x0, y0, t;
	vector<vector<int> > g(51 * 51 * 8);

	scanf("%d%d%d%d", &n, &x0, &y0, &t);
	for(int i = 0; i < n; ++i) {
		int ax, ay, bx, by;
		scanf("%d%d%d%d", &ax, &ay, &bx, &by);
		for(int x = min(ax, bx); x < max(ax, bx); ++x) {
			g[toidx(x, ay, 0, true)].push_back(toidx(x + 1, ay, 0, false));
			g[toidx(x + 1, ay, 2, true)].push_back(toidx(x, ay, 2, false));
		}
		for(int y = min(ay, by); y < max(ay, by); ++y) {
			g[toidx(ax, y, 1, true)].push_back(toidx(ax, y + 1, 1, false));
			g[toidx(ax, y + 1, 3, true)].push_back(toidx(ax, y, 3, false));
		}
	}
	for(int x = 0; x < 51; ++x) {
		for(int y = 0; y < 51; ++y) {
			for(int d1 = 0; d1 < 4; ++d1) {
				for(int d2 = 0; d2 < 4; ++d2) {
					if(d1 != d2 && d1 % 2 == d2 % 2)
						continue;
					g[toidx(x, y, d1, false)].push_back(toidx(x, y, d2, true));
				}
			}
		}
	}

	vector<bool> mem[2];
	mem[0].resize(51 * 51 * 8);
	mem[1].resize(51 * 51 * 8);

	for(int d = 0; d < 4; ++d)
		mem[0][toidx(x0, y0, d, true)] = true;

	for(int gps_step = 0; gps_step < t; ++gps_step) {

		char temp_buf[32];
		int dist, dir;
		scanf("%d%s", &dist, temp_buf);

		if(temp_buf[0] == 'E') dir = 0;
		if(temp_buf[0] == 'N') dir = 1;
		if(temp_buf[0] == 'W') dir = 2;
		if(temp_buf[0] == 'S') dir = 3;

		for(int step = 0; step < dist * 2; ++step) {

			vector<bool> &cur = mem[step % 2];
			vector<bool> &next = mem[(step + 1) % 2];
			fill(next.begin(), next.end(), false);

			for(int idx = 0; idx < 51 * 51 * 8; ++idx) {

				if(!cur[idx])
					continue;
				for(int i = 0; i < g[idx].size(); ++i) {
					int v = g[idx][i];
					if(step == dist * 2 - 1 && todir(idx) != dir && todir(v) != dir)
						continue;
					next[v] = true;
				}
			}
		}
	}

	for(int x = 0; x < 51; ++x) {
		for(int y = 0; y < 51; ++y) {
			for(int d = 0; d < 4; ++d) {
				int idx = toidx(x, y, d, true);
				if(mem[0][idx] && g[idx].size() > 0) {
					printf("%d %d\n", x, y);
					break;
				}
			}
		}
	}

	return 0;
}
### Prompt

Generate 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 <cstdio>
#include <vector>
#include <algorithm>
using namespace std;


inline int toidx(int x, int y, int d, int outnode)
{
	return (x * 51 + y) * 8 + d * 2 + outnode;
}

inline int todir(int idx)
{
	return (idx / 2) % 4;
}


int main()
{
	int n, x0, y0, t;
	vector<vector<int> > g(51 * 51 * 8);

	scanf("%d%d%d%d", &n, &x0, &y0, &t);
	for(int i = 0; i < n; ++i) {
		int ax, ay, bx, by;
		scanf("%d%d%d%d", &ax, &ay, &bx, &by);
		for(int x = min(ax, bx); x < max(ax, bx); ++x) {
			g[toidx(x, ay, 0, true)].push_back(toidx(x + 1, ay, 0, false));
			g[toidx(x + 1, ay, 2, true)].push_back(toidx(x, ay, 2, false));
		}
		for(int y = min(ay, by); y < max(ay, by); ++y) {
			g[toidx(ax, y, 1, true)].push_back(toidx(ax, y + 1, 1, false));
			g[toidx(ax, y + 1, 3, true)].push_back(toidx(ax, y, 3, false));
		}
	}
	for(int x = 0; x < 51; ++x) {
		for(int y = 0; y < 51; ++y) {
			for(int d1 = 0; d1 < 4; ++d1) {
				for(int d2 = 0; d2 < 4; ++d2) {
					if(d1 != d2 && d1 % 2 == d2 % 2)
						continue;
					g[toidx(x, y, d1, false)].push_back(toidx(x, y, d2, true));
				}
			}
		}
	}

	vector<bool> mem[2];
	mem[0].resize(51 * 51 * 8);
	mem[1].resize(51 * 51 * 8);

	for(int d = 0; d < 4; ++d)
		mem[0][toidx(x0, y0, d, true)] = true;

	for(int gps_step = 0; gps_step < t; ++gps_step) {

		char temp_buf[32];
		int dist, dir;
		scanf("%d%s", &dist, temp_buf);

		if(temp_buf[0] == 'E') dir = 0;
		if(temp_buf[0] == 'N') dir = 1;
		if(temp_buf[0] == 'W') dir = 2;
		if(temp_buf[0] == 'S') dir = 3;

		for(int step = 0; step < dist * 2; ++step) {

			vector<bool> &cur = mem[step % 2];
			vector<bool> &next = mem[(step + 1) % 2];
			fill(next.begin(), next.end(), false);

			for(int idx = 0; idx < 51 * 51 * 8; ++idx) {

				if(!cur[idx])
					continue;
				for(int i = 0; i < g[idx].size(); ++i) {
					int v = g[idx][i];
					if(step == dist * 2 - 1 && todir(idx) != dir && todir(v) != dir)
						continue;
					next[v] = true;
				}
			}
		}
	}

	for(int x = 0; x < 51; ++x) {
		for(int y = 0; y < 51; ++y) {
			for(int d = 0; d < 4; ++d) {
				int idx = toidx(x, y, d, true);
				if(mem[0][idx] && g[idx].size() > 0) {
					printf("%d %d\n", x, y);
					break;
				}
			}
		}
	}

	return 0;
}
```