#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
typedef pair<int,int> P;
typedef pair<P,P> PP;
vector<PP> vc,nvc;
bool e[51][51][4];
bool vis[51][51][4][2][11];
void dfs(int x,int y,int d,bool m,int t){		//m=magatta
	if(vis[x][y][d][m][t]) return;
	vis[x][y][d][m][t]=1;
	if(t==0){
		nvc.pb(PP(P(x,y),P(d,m)));
	}
	if(!m){
		for(int i=d+1;i<=d+3;i+=2){
			if(e[x][y][i%4]) dfs(x,y,i%4,1,t);
		}
	}
	if(t&&e[x][y][d]){
		int nx=x+dx[d],ny=y+dy[d];
		dfs(nx,ny,d,0,t-1);
	}
}
int main(){
	int N,sx,sy,T;
	cin>>N>>sx>>sy>>T;
	rep(i,N){
		int a,b,c,d;
		cin>>a>>b>>c>>d;
		if(a==c){
			if(b>d) swap(b,d);
			for(int j=b;j<d;j++) e[a][j][1]=e[a][j+1][3]=1;
		}else{
			if(a>c) swap(a,c);
			for(int j=a;j<c;j++) e[j][b][0]=e[j+1][b][2]=1;
		}
	}
	rep(i,4) vc.pb(PP(P(sx,sy),P(i,1)));
	rep(tt,T){
		rep(i,51) rep(j,51) rep(k,4) rep(l,2) rep(m,11) vis[i][j][k][l][m]=0;
		int t;
		char c;
		cin>>t>>c;
		int dir=-1;
		if(c=='E') dir=0;
		if(c=='N') dir=1;
		if(c=='W') dir=2;
		if(c=='S') dir=3;
		for(PP pp:vc){
			dfs(pp.fs.fs,pp.fs.sc,pp.sc.fs,pp.sc.sc,t);
		}
		vc.clear();
		for(PP pp:nvc){
			if(pp.sc.fs==dir) vc.pb(pp);
		}
		nvc.clear();
	}
	vector<P> ans;
	for(PP pp:vc) ans.pb(pp.fs);
	sort(all(ans));
	ans.erase(unique(all(ans)),ans.end());
	for(P p:ans){
		cout<<p.fs<<" "<<p.sc<<endl;
	}
}
### Prompt

Create a solution in Cpp for 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>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
typedef pair<int,int> P;
typedef pair<P,P> PP;
vector<PP> vc,nvc;
bool e[51][51][4];
bool vis[51][51][4][2][11];
void dfs(int x,int y,int d,bool m,int t){		//m=magatta
	if(vis[x][y][d][m][t]) return;
	vis[x][y][d][m][t]=1;
	if(t==0){
		nvc.pb(PP(P(x,y),P(d,m)));
	}
	if(!m){
		for(int i=d+1;i<=d+3;i+=2){
			if(e[x][y][i%4]) dfs(x,y,i%4,1,t);
		}
	}
	if(t&&e[x][y][d]){
		int nx=x+dx[d],ny=y+dy[d];
		dfs(nx,ny,d,0,t-1);
	}
}
int main(){
	int N,sx,sy,T;
	cin>>N>>sx>>sy>>T;
	rep(i,N){
		int a,b,c,d;
		cin>>a>>b>>c>>d;
		if(a==c){
			if(b>d) swap(b,d);
			for(int j=b;j<d;j++) e[a][j][1]=e[a][j+1][3]=1;
		}else{
			if(a>c) swap(a,c);
			for(int j=a;j<c;j++) e[j][b][0]=e[j+1][b][2]=1;
		}
	}
	rep(i,4) vc.pb(PP(P(sx,sy),P(i,1)));
	rep(tt,T){
		rep(i,51) rep(j,51) rep(k,4) rep(l,2) rep(m,11) vis[i][j][k][l][m]=0;
		int t;
		char c;
		cin>>t>>c;
		int dir=-1;
		if(c=='E') dir=0;
		if(c=='N') dir=1;
		if(c=='W') dir=2;
		if(c=='S') dir=3;
		for(PP pp:vc){
			dfs(pp.fs.fs,pp.fs.sc,pp.sc.fs,pp.sc.sc,t);
		}
		vc.clear();
		for(PP pp:nvc){
			if(pp.sc.fs==dir) vc.pb(pp);
		}
		nvc.clear();
	}
	vector<P> ans;
	for(PP pp:vc) ans.pb(pp.fs);
	sort(all(ans));
	ans.erase(unique(all(ans)),ans.end());
	for(P p:ans){
		cout<<p.fs<<" "<<p.sc<<endl;
	}
}
```