#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <utility>
#include <set>
using namespace std;

#define MP make_pair

bool flag[53][53][4];

int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};

int main(){
	int n,x0,y0,t;
	cin >> n >> x0 >> y0 >> t;
	x0++;
	y0++;
	for(int k=0;k<n;k++){
		int a,b,c,d;
		cin >> a >> b >> c >> d;
		a++;b++;c++;d++;
		if(a==c){
			if(b>d)swap(b,d);
			for(int i=b;i<d;i++){
				flag[a][i][0] = 1;
			}
			for(int i=d;i>b;i--){
				flag[a][i][2] = 1;
			}
		}
		if(b==d){
			if(a>c)swap(a,c);
			for(int i=a;i<c;i++){
				flag[i][b][1] = 1;
			}
			for(int i=c;i>a;i--){
				flag[i][b][3] = 1;
			}
		}
	}
	map<int,int> mp;
	int s = 0;
	for(int i=0;i<t;i++){
		int a;
		cin >> a;
		char b;
		cin >> b;
		s += a;
		if(b=='N'){
			mp[s] = 0;
		}else if(b=='E'){
			mp[s] = 1;
		}else if(b=='S'){
			mp[s] = 2;
		}else{
			mp[s] = 3;
		}
	}
	queue<pair<pair<int,int>,pair<int,int> > >q;
	map<pair<pair<int,int>,pair<int,int> >,bool> m;
	if(flag[x0][y0][0]==1){
		q.push(MP(MP(x0,y0),MP(0,0)));
	}
	if(flag[x0][y0][1]==1){
		q.push(MP(MP(x0,y0),MP(0,1)));
	}
	if(flag[x0][y0][2]==1){
		q.push(MP(MP(x0,y0),MP(0,2)));
	}
	if(flag[x0][y0][3]==1){
		q.push(MP(MP(x0,y0),MP(0,3)));
	}
	set<pair<int,int> > ans;
	while(1){
		auto x = q.front();
		q.pop();
		int a,b,c,d;
		a = x.first.first;
		b = x.first.second;
		c = x.second.first;
		d = x.second.second;
		//cout << a <<" " << b << " " <<c << " " << d << endl;
		if(c>s)break;
		if(c==s){
			ans.insert(MP(a-1,b-1));
		}
		if(mp.find(c+1)!=mp.end()){
			if(d==mp[c+1]){
				for(int i=0;i<4;i++){
					if(i!=d&&(i+4-d)%2==0)continue;
					if(flag[a+dx[d]][b+dy[d]][i]==1&&m[MP(MP(a+dx[d],b+dy[d]),MP(c+1,i))]==0){
						m[MP(MP(a+dx[d],b+dy[d]),MP(c+1,i))]=1;
						q.push(MP(MP(a+dx[d],b+dy[d]),MP(c+1,i)));
					}
				}
			}else{
				if((d+4-mp[c+1])%2!=0&&flag[a+dx[d]][b+dy[d]][mp[c+1]]==1&&m[MP(MP(a+dx[d],b+dy[d]),MP(c+1,mp[c+1]))]==0){
					m[MP(MP(a+dx[d],b+dy[d]),MP(c+1,mp[c+1]))]=1;
					q.push(MP(MP(a+dx[d],b+dy[d]),MP(c+1,mp[c+1])));
				}
			}
		}else{
			for(int i=0;i<4;i++){
				if(i!=d&&(i+4-d)%2==0)continue;
				if(flag[a+dx[d]][b+dy[d]][i]==1&&m[MP(MP(a+dx[d],b+dy[d]),MP(c+1,i))]==0){
					m[MP(MP(a+dx[d],b+dy[d]),MP(c+1,i))]=1;
					q.push(MP(MP(a+dx[d],b+dy[d]),MP(c+1,i)));
				}
			}
		}
	}
	for(auto x:ans){
		cout << x.first << " " << x.second << endl;
	}
	return 0;
}

### 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 <iostream>
#include <vector>
#include <map>
#include <queue>
#include <utility>
#include <set>
using namespace std;

#define MP make_pair

bool flag[53][53][4];

int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};

int main(){
	int n,x0,y0,t;
	cin >> n >> x0 >> y0 >> t;
	x0++;
	y0++;
	for(int k=0;k<n;k++){
		int a,b,c,d;
		cin >> a >> b >> c >> d;
		a++;b++;c++;d++;
		if(a==c){
			if(b>d)swap(b,d);
			for(int i=b;i<d;i++){
				flag[a][i][0] = 1;
			}
			for(int i=d;i>b;i--){
				flag[a][i][2] = 1;
			}
		}
		if(b==d){
			if(a>c)swap(a,c);
			for(int i=a;i<c;i++){
				flag[i][b][1] = 1;
			}
			for(int i=c;i>a;i--){
				flag[i][b][3] = 1;
			}
		}
	}
	map<int,int> mp;
	int s = 0;
	for(int i=0;i<t;i++){
		int a;
		cin >> a;
		char b;
		cin >> b;
		s += a;
		if(b=='N'){
			mp[s] = 0;
		}else if(b=='E'){
			mp[s] = 1;
		}else if(b=='S'){
			mp[s] = 2;
		}else{
			mp[s] = 3;
		}
	}
	queue<pair<pair<int,int>,pair<int,int> > >q;
	map<pair<pair<int,int>,pair<int,int> >,bool> m;
	if(flag[x0][y0][0]==1){
		q.push(MP(MP(x0,y0),MP(0,0)));
	}
	if(flag[x0][y0][1]==1){
		q.push(MP(MP(x0,y0),MP(0,1)));
	}
	if(flag[x0][y0][2]==1){
		q.push(MP(MP(x0,y0),MP(0,2)));
	}
	if(flag[x0][y0][3]==1){
		q.push(MP(MP(x0,y0),MP(0,3)));
	}
	set<pair<int,int> > ans;
	while(1){
		auto x = q.front();
		q.pop();
		int a,b,c,d;
		a = x.first.first;
		b = x.first.second;
		c = x.second.first;
		d = x.second.second;
		//cout << a <<" " << b << " " <<c << " " << d << endl;
		if(c>s)break;
		if(c==s){
			ans.insert(MP(a-1,b-1));
		}
		if(mp.find(c+1)!=mp.end()){
			if(d==mp[c+1]){
				for(int i=0;i<4;i++){
					if(i!=d&&(i+4-d)%2==0)continue;
					if(flag[a+dx[d]][b+dy[d]][i]==1&&m[MP(MP(a+dx[d],b+dy[d]),MP(c+1,i))]==0){
						m[MP(MP(a+dx[d],b+dy[d]),MP(c+1,i))]=1;
						q.push(MP(MP(a+dx[d],b+dy[d]),MP(c+1,i)));
					}
				}
			}else{
				if((d+4-mp[c+1])%2!=0&&flag[a+dx[d]][b+dy[d]][mp[c+1]]==1&&m[MP(MP(a+dx[d],b+dy[d]),MP(c+1,mp[c+1]))]==0){
					m[MP(MP(a+dx[d],b+dy[d]),MP(c+1,mp[c+1]))]=1;
					q.push(MP(MP(a+dx[d],b+dy[d]),MP(c+1,mp[c+1])));
				}
			}
		}else{
			for(int i=0;i<4;i++){
				if(i!=d&&(i+4-d)%2==0)continue;
				if(flag[a+dx[d]][b+dy[d]][i]==1&&m[MP(MP(a+dx[d],b+dy[d]),MP(c+1,i))]==0){
					m[MP(MP(a+dx[d],b+dy[d]),MP(c+1,i))]=1;
					q.push(MP(MP(a+dx[d],b+dy[d]),MP(c+1,i)));
				}
			}
		}
	}
	for(auto x:ans){
		cout << x.first << " " << x.second << endl;
	}
	return 0;
}

```