#include  <bits/stdc++.h>
#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)
using namespace std;

const int limit=55;
const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};

bool dist[limit][limit][4],ndist[limit][limit][4];
bool can[limit][limit][4];

void move(int n,int c){
	rep(loop,n-1){
		rep(x,limit)rep(y,limit)rep(d,4){
			if(dist[x][y][d]==false) continue;
			if(can[x][y][d]==false) continue; 
			int nx=x+dx[d],ny=y+dy[d];
			if(can[nx][ny][d]) ndist[nx][ny][d]=true;
			if(can[nx][ny][(d+1)%4]) ndist[nx][ny][(d+1)%4]=true;
			if(can[nx][ny][(d+3)%4]) ndist[nx][ny][(d+3)%4]=true;
		}
		rep(x,limit)rep(y,limit)rep(d,4) dist[x][y][d]=ndist[x][y][d],ndist[x][y][d]=false;
	}
	rep(x,limit)rep(y,limit)rep(d,4){
		if(dist[x][y][d]==false) continue;
		if(can[x][y][d]==false) continue; 
		int nx=x+dx[d],ny=y+dy[d];
		if(d==c&&can[nx][ny][d]) ndist[nx][ny][d]=true;
		if( (d==c||(d+1)%4==c)&&can[nx][ny][(d+1)%4]) ndist[nx][ny][(d+1)%4]=true;
		if( (d==c||(d+3)%4==c)&&can[nx][ny][(d+3)%4]) ndist[nx][ny][(d+3)%4]=true;
	} 
	rep(x,limit)rep(y,limit)rep(d,4) dist[x][y][d]=ndist[x][y][d],ndist[x][y][d]=false;
}

int main(void){
	int n,cx,cy,t;
	cin >> n >> cx >> cy >> t;
	rep(d,4) dist[cx][cy][d]=true;
	rep(i,n){
		int sx,sy,gx,gy;
		cin >> sx >> sy >> gx >> gy;
		if(sy==gy) rep(x,min(sx,gx),max(sx,gx)) can[x][sy][0]=true,can[x+1][sy][2]=true;
		if(sx==gx) rep(y,min(sy,gy),max(sy,gy)) can[sx][y][1]=true,can[sx][y+1][3]=true;
	}
	rep(loop,t){
		int m; char c;
		cin >> m >> c;
		if(c=='E') move(m,0);
		if(c=='N') move(m,1);
		if(c=='W') move(m,2);
		if(c=='S') move(m,3);
	}
	rep(x,limit)rep(y,limit){
		bool ok=false;
		rep(d,4) if(dist[x][y][d]) ok=true;
		if(ok) cout << x << " " << y << endl;
	}
	return 0;
}
### Prompt

Your challenge is to write 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>
#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)
using namespace std;

const int limit=55;
const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};

bool dist[limit][limit][4],ndist[limit][limit][4];
bool can[limit][limit][4];

void move(int n,int c){
	rep(loop,n-1){
		rep(x,limit)rep(y,limit)rep(d,4){
			if(dist[x][y][d]==false) continue;
			if(can[x][y][d]==false) continue; 
			int nx=x+dx[d],ny=y+dy[d];
			if(can[nx][ny][d]) ndist[nx][ny][d]=true;
			if(can[nx][ny][(d+1)%4]) ndist[nx][ny][(d+1)%4]=true;
			if(can[nx][ny][(d+3)%4]) ndist[nx][ny][(d+3)%4]=true;
		}
		rep(x,limit)rep(y,limit)rep(d,4) dist[x][y][d]=ndist[x][y][d],ndist[x][y][d]=false;
	}
	rep(x,limit)rep(y,limit)rep(d,4){
		if(dist[x][y][d]==false) continue;
		if(can[x][y][d]==false) continue; 
		int nx=x+dx[d],ny=y+dy[d];
		if(d==c&&can[nx][ny][d]) ndist[nx][ny][d]=true;
		if( (d==c||(d+1)%4==c)&&can[nx][ny][(d+1)%4]) ndist[nx][ny][(d+1)%4]=true;
		if( (d==c||(d+3)%4==c)&&can[nx][ny][(d+3)%4]) ndist[nx][ny][(d+3)%4]=true;
	} 
	rep(x,limit)rep(y,limit)rep(d,4) dist[x][y][d]=ndist[x][y][d],ndist[x][y][d]=false;
}

int main(void){
	int n,cx,cy,t;
	cin >> n >> cx >> cy >> t;
	rep(d,4) dist[cx][cy][d]=true;
	rep(i,n){
		int sx,sy,gx,gy;
		cin >> sx >> sy >> gx >> gy;
		if(sy==gy) rep(x,min(sx,gx),max(sx,gx)) can[x][sy][0]=true,can[x+1][sy][2]=true;
		if(sx==gx) rep(y,min(sy,gy),max(sy,gy)) can[sx][y][1]=true,can[sx][y+1][3]=true;
	}
	rep(loop,t){
		int m; char c;
		cin >> m >> c;
		if(c=='E') move(m,0);
		if(c=='N') move(m,1);
		if(c=='W') move(m,2);
		if(c=='S') move(m,3);
	}
	rep(x,limit)rep(y,limit){
		bool ok=false;
		rep(d,4) if(dist[x][y][d]) ok=true;
		if(ok) cout << x << " " << y << endl;
	}
	return 0;
}
```