#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (int)(k); i < (int)(n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
const int MOD = 1000000007;
const int INF = MOD + 1;
const ld EPS = 1e-12;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }

/*--------------------template--------------------*/
const int dx[] = { 0, -1, 1, 0 }, dy[] = { 1, 0, 0, -1 };
//[const int dx[] = { -1, -1, -1, 0, 0, 1, 1, 1 }, dy[] = { 0, -1, 1, -1, 1, 0, -1, 1 };
bool valid(int x, int y, int h, int w) { return (x >= 0 && y >= 0 && x < h&&y < w); }
int place(int x, int y, int w) { return w*x + y; }

typedef tuple<int, int, int, int> state;


int dist(pii a, pii b)
{
	return abs(a.first - b.first) + abs(a.second - b.second);
}

void adv(int& x, int& y, int dir, int d)
{
	if (dir == 0) y += d;
	if (dir == 1) x -= d;
	if (dir == 2) x += d;
	if (dir == 3) y -= d;
}

typedef pair<pii, pii> seg;

pii is_ss(seg a, seg b)
{
	if (a.first.first >= b.first.first && a.first.first <= b.second.first &&
		b.first.second >= a.first.second && b.first.second <= a.second.second)
	{
		return pii(a.first.first, b.first.second);
	}
	else
	{
		return pii(-1, -1);
	}
}

int main()
{
	cin.sync_with_stdio(false); cout << fixed << setprecision(10);
	int n, x0, y0, t;
	cin >> n >> x0 >> y0 >> t;
	int edge[55][55][4];
	MS(edge, -1);
	set<pii> ver;
	vector<seg> yoko, tate;

	REP(i, n)
	{
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		ver.emplace(a, b);
		ver.emplace(c, d);
		if (a == c)
		{
			if (b > d) swap(b, d);
			tate.emplace_back(pii(a, b), pii(c, d));
		}
		else
		{
			if (a > c) swap(a, c);
			yoko.emplace_back(pii(a, b), pii(c, d));
		}
	}
	for (auto i : tate)for (auto j : yoko)
	{
		pii tmp = is_ss(i, j);
		if (tmp == pii(-1, -1)) continue;
		else ver.emplace(tmp);
	}

	REP(i, 55)REP(j, 55)
	{
		for (auto k : tate)
		{
			if (k.first.first != i || k.first.second > j || k.second.second < j) continue;
			vi dir;
			if (k.second.second > j) dir.push_back(0);
			if (k.first.second < j) dir.push_back(3);
			for (auto l : dir)
			{
				if (!valid(i + dx[l], j + dy[l], 55, 55)) continue;
				int tx = i + dx[l], ty = j + dy[l];
				while (ver.count(pii(tx, ty)) == 0)
				{
					tx += dx[l], ty += dy[l];
				}
				edge[i][j][l] = dist(pii(i, j), pii(tx, ty));
			}
		}
		for (auto k : yoko)
		{
			if (k.first.second != j || k.first.first > i || k.second.first < i) continue;
			vi dir;
			if (k.second.first > i) dir.push_back(2);
			if (k.first.first < i) dir.push_back(1);
			for (auto l : dir)
			{
				if (!valid(i + dx[l], j + dy[l], 55, 55)) continue;
				int tx = i + dx[l], ty = j + dy[l];
				while (ver.count(pii(tx, ty)) == 0)
				{
					tx += dx[l], ty += dy[l];
				}
				edge[i][j][l] = dist(pii(i, j), pii(tx, ty));
			}
		}
	}
	vector<pii> v;
	REP(i, t)
	{
		int a, b; char c;
		cin >> a >> c;
		if (c == 'N') b = 0;
		if (c == 'W') b = 1;
		if (c == 'E') b = 2;
		if (c == 'S') b = 3;
		v.emplace_back(a, b);
	}
	queue<state> que;
	REP(i, 4)
	{
		if (edge[x0][y0][i] == -1) continue;
		que.push(state(x0, y0, i, 0));
	}
	for (auto i : v)
	{
		set<state> finish, rem;
		while (!que.empty())
		{
			auto tmp = que.front(); que.pop();
			int x, y, dir, time;
			tie(x, y, dir, time) = tmp;
			if (edge[x][y][dir] > i.first - time)
			{
				adv(x, y, dir, i.first - time);
				if(dir == i.second) finish.emplace(x, y, dir, 0);
			}
			else if (edge[x][y][dir] == i.first - time)
			{
				adv(x, y, dir, edge[x][y][dir]);
				set<int> stdir;
				REP(j, 4)
				{
					if (edge[x][y][j] >= 0) stdir.insert(j);
				}
				stdir.erase(3 - dir);
				if (dir == i.second)
				{
					for (auto j : stdir) finish.emplace(x, y, j, 0);
				}
				else if (stdir.count(i.second)) finish.emplace(x, y, i.second, 0);
			}
			else
			{
				int ad = edge[x][y][dir];
				adv(x, y, dir, ad);
				set<int> stdir;
				REP(j, 4)
				{
					if (edge[x][y][j] >= 0) stdir.insert(j);
				}
				stdir.erase(3 - dir);
				for (auto j : stdir)
				{
					if (rem.count(state(x, y, j, time + ad))) continue;
					rem.emplace(x, y, j, time + ad);
					que.emplace(x, y, j, time + ad);
				}
			}
		}
		for (auto j : finish) que.push(j);
	}
	set<pii> ans;
	while (!que.empty())
	{
		auto tmp = que.front(); que.pop();
		ans.emplace(get<0>(tmp), get<1>(tmp));
	}
	for (auto i : ans)
	{
		cout << i.first << " " << i.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>
using namespace std;
#define FOR(i,k,n) for(int i = (int)(k); i < (int)(n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
const int MOD = 1000000007;
const int INF = MOD + 1;
const ld EPS = 1e-12;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }

/*--------------------template--------------------*/
const int dx[] = { 0, -1, 1, 0 }, dy[] = { 1, 0, 0, -1 };
//[const int dx[] = { -1, -1, -1, 0, 0, 1, 1, 1 }, dy[] = { 0, -1, 1, -1, 1, 0, -1, 1 };
bool valid(int x, int y, int h, int w) { return (x >= 0 && y >= 0 && x < h&&y < w); }
int place(int x, int y, int w) { return w*x + y; }

typedef tuple<int, int, int, int> state;


int dist(pii a, pii b)
{
	return abs(a.first - b.first) + abs(a.second - b.second);
}

void adv(int& x, int& y, int dir, int d)
{
	if (dir == 0) y += d;
	if (dir == 1) x -= d;
	if (dir == 2) x += d;
	if (dir == 3) y -= d;
}

typedef pair<pii, pii> seg;

pii is_ss(seg a, seg b)
{
	if (a.first.first >= b.first.first && a.first.first <= b.second.first &&
		b.first.second >= a.first.second && b.first.second <= a.second.second)
	{
		return pii(a.first.first, b.first.second);
	}
	else
	{
		return pii(-1, -1);
	}
}

int main()
{
	cin.sync_with_stdio(false); cout << fixed << setprecision(10);
	int n, x0, y0, t;
	cin >> n >> x0 >> y0 >> t;
	int edge[55][55][4];
	MS(edge, -1);
	set<pii> ver;
	vector<seg> yoko, tate;

	REP(i, n)
	{
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		ver.emplace(a, b);
		ver.emplace(c, d);
		if (a == c)
		{
			if (b > d) swap(b, d);
			tate.emplace_back(pii(a, b), pii(c, d));
		}
		else
		{
			if (a > c) swap(a, c);
			yoko.emplace_back(pii(a, b), pii(c, d));
		}
	}
	for (auto i : tate)for (auto j : yoko)
	{
		pii tmp = is_ss(i, j);
		if (tmp == pii(-1, -1)) continue;
		else ver.emplace(tmp);
	}

	REP(i, 55)REP(j, 55)
	{
		for (auto k : tate)
		{
			if (k.first.first != i || k.first.second > j || k.second.second < j) continue;
			vi dir;
			if (k.second.second > j) dir.push_back(0);
			if (k.first.second < j) dir.push_back(3);
			for (auto l : dir)
			{
				if (!valid(i + dx[l], j + dy[l], 55, 55)) continue;
				int tx = i + dx[l], ty = j + dy[l];
				while (ver.count(pii(tx, ty)) == 0)
				{
					tx += dx[l], ty += dy[l];
				}
				edge[i][j][l] = dist(pii(i, j), pii(tx, ty));
			}
		}
		for (auto k : yoko)
		{
			if (k.first.second != j || k.first.first > i || k.second.first < i) continue;
			vi dir;
			if (k.second.first > i) dir.push_back(2);
			if (k.first.first < i) dir.push_back(1);
			for (auto l : dir)
			{
				if (!valid(i + dx[l], j + dy[l], 55, 55)) continue;
				int tx = i + dx[l], ty = j + dy[l];
				while (ver.count(pii(tx, ty)) == 0)
				{
					tx += dx[l], ty += dy[l];
				}
				edge[i][j][l] = dist(pii(i, j), pii(tx, ty));
			}
		}
	}
	vector<pii> v;
	REP(i, t)
	{
		int a, b; char c;
		cin >> a >> c;
		if (c == 'N') b = 0;
		if (c == 'W') b = 1;
		if (c == 'E') b = 2;
		if (c == 'S') b = 3;
		v.emplace_back(a, b);
	}
	queue<state> que;
	REP(i, 4)
	{
		if (edge[x0][y0][i] == -1) continue;
		que.push(state(x0, y0, i, 0));
	}
	for (auto i : v)
	{
		set<state> finish, rem;
		while (!que.empty())
		{
			auto tmp = que.front(); que.pop();
			int x, y, dir, time;
			tie(x, y, dir, time) = tmp;
			if (edge[x][y][dir] > i.first - time)
			{
				adv(x, y, dir, i.first - time);
				if(dir == i.second) finish.emplace(x, y, dir, 0);
			}
			else if (edge[x][y][dir] == i.first - time)
			{
				adv(x, y, dir, edge[x][y][dir]);
				set<int> stdir;
				REP(j, 4)
				{
					if (edge[x][y][j] >= 0) stdir.insert(j);
				}
				stdir.erase(3 - dir);
				if (dir == i.second)
				{
					for (auto j : stdir) finish.emplace(x, y, j, 0);
				}
				else if (stdir.count(i.second)) finish.emplace(x, y, i.second, 0);
			}
			else
			{
				int ad = edge[x][y][dir];
				adv(x, y, dir, ad);
				set<int> stdir;
				REP(j, 4)
				{
					if (edge[x][y][j] >= 0) stdir.insert(j);
				}
				stdir.erase(3 - dir);
				for (auto j : stdir)
				{
					if (rem.count(state(x, y, j, time + ad))) continue;
					rem.emplace(x, y, j, time + ad);
					que.emplace(x, y, j, time + ad);
				}
			}
		}
		for (auto j : finish) que.push(j);
	}
	set<pii> ans;
	while (!que.empty())
	{
		auto tmp = que.front(); que.pop();
		ans.emplace(get<0>(tmp), get<1>(tmp));
	}
	for (auto i : ans)
	{
		cout << i.first << " " << i.second << endl;
	}
	return 0;
}
```