#include <cstdlib>
#include <iostream>
#include <numeric>
#include <set>
#include <vector>
using namespace std;

typedef pair<int, int> point;
#define X first
#define Y second

inline point operator+(const point &a, const point &b) {
	return point(a.X + b.X, a.Y + b.Y);
}

enum { N, E, S, W, D };
const point dv[] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

char convert[128];

constexpr int MAX_D = 10;
constexpr int MAX_T = 100;
constexpr int MAX_C = 50;

bool can_move[MAX_C + 1][MAX_C + 1][D];
set<point> dp[MAX_D * MAX_T + 1][D];

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

	convert['N'] = N;
	convert['E'] = E;
	convert['S'] = S;
	convert['W'] = W;

	int n, sx, sy, t;
	cin >> n >> sx >> sy >> t;

	for(int i = 0; i < n; ++i) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;

		if(x1 == x2) {
			if(y1 > y2) swap(y1, y2);

			for(int y = y1; y <= y2; ++y) {
				if(y > y1) can_move[y][x1][S] = true;
				if(y < y2) can_move[y][x1][N] = true;
			}
		}
		else {
			if(x1 > x2) swap(x1, x2);

			for(int x = x1; x <= x2; ++x) {
				if(x > x1) can_move[y1][x][W] = true;
				if(x < x2) can_move[y1][x][E] = true;
			}
		}
	}

	vector<int> dist(t);
	vector<int> direction(t);

	for(int i = 0; i < t; ++i) {
		char c;
		cin >> dist[i] >> c;
		direction[i] = convert[c];
	}

	partial_sum(begin(dist), end(dist), begin(dist));

	for(int dir = 0; dir < D; ++dir) {
		dp[0][dir].insert(point(sx, sy));
	}

	int check_index = 0;
	for(int d = 0; d < dist.back(); ++d) {
		const bool is_check_time = (d == dist[check_index]);

		for(int dir = 0; dir < D; ++dir) {
			for(int next_dir = 0; next_dir < D; ++next_dir) {
				if((dir ^ next_dir) == 2) continue;
				if(is_check_time && (dir != direction[check_index] && next_dir != direction[check_index])) continue;

				for(const auto &p : dp[d][dir]) {
					if(!can_move[p.Y][p.X][next_dir]) continue;
					dp[d + 1][next_dir].insert(p + dv[next_dir]);
				}
			}
			dp[d][dir].clear();
		}

		if(is_check_time) ++check_index;
	}

	set<point> ans;
	for(int dir = 0; dir < D; ++dir) {
		if((dir ^ direction.back()) == 2) continue;

		for(const auto &p : dp[dist.back()][dir]) {
			if(dir == direction.back() || can_move[p.Y][p.X][direction.back()]) {
				ans.insert(p);
			}
		}
	}

	for(const auto &p : ans) {
		cout << p.X << " " << p.Y << endl;
	}

	return EXIT_SUCCESS;
}
### Prompt

Construct a cpp code solution to the problem outlined:

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 <cstdlib>
#include <iostream>
#include <numeric>
#include <set>
#include <vector>
using namespace std;

typedef pair<int, int> point;
#define X first
#define Y second

inline point operator+(const point &a, const point &b) {
	return point(a.X + b.X, a.Y + b.Y);
}

enum { N, E, S, W, D };
const point dv[] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

char convert[128];

constexpr int MAX_D = 10;
constexpr int MAX_T = 100;
constexpr int MAX_C = 50;

bool can_move[MAX_C + 1][MAX_C + 1][D];
set<point> dp[MAX_D * MAX_T + 1][D];

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

	convert['N'] = N;
	convert['E'] = E;
	convert['S'] = S;
	convert['W'] = W;

	int n, sx, sy, t;
	cin >> n >> sx >> sy >> t;

	for(int i = 0; i < n; ++i) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;

		if(x1 == x2) {
			if(y1 > y2) swap(y1, y2);

			for(int y = y1; y <= y2; ++y) {
				if(y > y1) can_move[y][x1][S] = true;
				if(y < y2) can_move[y][x1][N] = true;
			}
		}
		else {
			if(x1 > x2) swap(x1, x2);

			for(int x = x1; x <= x2; ++x) {
				if(x > x1) can_move[y1][x][W] = true;
				if(x < x2) can_move[y1][x][E] = true;
			}
		}
	}

	vector<int> dist(t);
	vector<int> direction(t);

	for(int i = 0; i < t; ++i) {
		char c;
		cin >> dist[i] >> c;
		direction[i] = convert[c];
	}

	partial_sum(begin(dist), end(dist), begin(dist));

	for(int dir = 0; dir < D; ++dir) {
		dp[0][dir].insert(point(sx, sy));
	}

	int check_index = 0;
	for(int d = 0; d < dist.back(); ++d) {
		const bool is_check_time = (d == dist[check_index]);

		for(int dir = 0; dir < D; ++dir) {
			for(int next_dir = 0; next_dir < D; ++next_dir) {
				if((dir ^ next_dir) == 2) continue;
				if(is_check_time && (dir != direction[check_index] && next_dir != direction[check_index])) continue;

				for(const auto &p : dp[d][dir]) {
					if(!can_move[p.Y][p.X][next_dir]) continue;
					dp[d + 1][next_dir].insert(p + dv[next_dir]);
				}
			}
			dp[d][dir].clear();
		}

		if(is_check_time) ++check_index;
	}

	set<point> ans;
	for(int dir = 0; dir < D; ++dir) {
		if((dir ^ direction.back()) == 2) continue;

		for(const auto &p : dp[dist.back()][dir]) {
			if(dir == direction.back() || can_move[p.Y][p.X][direction.back()]) {
				ans.insert(p);
			}
		}
	}

	for(const auto &p : ans) {
		cout << p.X << " " << p.Y << endl;
	}

	return EXIT_SUCCESS;
}
```