// ACM-ICPCアジア地区予選2014 E. Automotive Navigation

#include <iostream>
#include <cstring>

using namespace std;

int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
int getDir(char c){
	if(c == 'N') return 0;
	if(c == 'E') return 1;
	if(c == 'S') return 2;
	return 3;
}

int main(){
	int n, x0, y0, t;
	int mp[51][51];
	int visit[2][51][51];
	while(cin >> n >> x0 >> y0 >> t){
		memset(mp, 0, sizeof(mp));
		memset(visit, 0, sizeof(visit));
		visit[0][x0][y0] = 15;
		for(int i=0;i<n;i++){
			int xs, ys, xe, ye; cin >> xs >> ys >> xe >> ye;
			if(xs > xe) swap(xs, xe);
			if(ys > ye) swap(ys, ye);
			if(xs == xe){
				for(int i=ys;i<ye;i++){
					mp[xs][i  ] |= (1<<0);
					mp[xs][i+1] |= (1<<2);
				}
			} else {
				for(int i=xs;i<xe;i++){
					mp[i  ][ys] |= (1<<1);
					mp[i+1][ys] |= (1<<3);
				}
			}
		}
		int cur = 0, next = 1;
		for(int i=0;i<t;i++){
			int d; char c; cin >> d >> c;
			int targetDir = getDir(c);
			for(int j=0;j<d;j++){
				memset(visit[next], 0, sizeof(visit[next]));
				for(int x=0;x<=50;x++){
					for(int y=0;y<=50;y++){
						for(int dir=0;dir<4;dir++){
							if(!(visit[cur][x][y]&(1<<dir))) continue;
							if(!(mp[x][y]&(1<<dir))) continue;
							int nx = x+dx[dir], ny = y+dy[dir];
							visit[next][nx][ny] |= (1<<dir);
						}
					}
				}
				for(int x=0;x<=50;x++){
					for(int y=0;y<=50;y++){
						int nmask = 0;
						for(int dir=0;dir<4;dir++){
							if(!(visit[next][x][y]&(1<<dir))) continue;
							int mask = (15^(1<<((dir+2)%4)))&mp[x][y];
							if(j==d-1 && dir != targetDir) mask &= (1<< targetDir);
							nmask |= mask;
						}
						visit[next][x][y] = nmask;
					}
				}
				swap(cur, next);
			}
		}
		for(int x=0;x<=50;x++){
			for(int y=0;y<=50;y++){
				if(visit[cur][x][y]) cout << x << " " << y << endl;
			}
		}
	}
}
### Prompt

Develop a solution in Cpp to the problem described below:

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
// ACM-ICPCアジア地区予選2014 E. Automotive Navigation

#include <iostream>
#include <cstring>

using namespace std;

int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
int getDir(char c){
	if(c == 'N') return 0;
	if(c == 'E') return 1;
	if(c == 'S') return 2;
	return 3;
}

int main(){
	int n, x0, y0, t;
	int mp[51][51];
	int visit[2][51][51];
	while(cin >> n >> x0 >> y0 >> t){
		memset(mp, 0, sizeof(mp));
		memset(visit, 0, sizeof(visit));
		visit[0][x0][y0] = 15;
		for(int i=0;i<n;i++){
			int xs, ys, xe, ye; cin >> xs >> ys >> xe >> ye;
			if(xs > xe) swap(xs, xe);
			if(ys > ye) swap(ys, ye);
			if(xs == xe){
				for(int i=ys;i<ye;i++){
					mp[xs][i  ] |= (1<<0);
					mp[xs][i+1] |= (1<<2);
				}
			} else {
				for(int i=xs;i<xe;i++){
					mp[i  ][ys] |= (1<<1);
					mp[i+1][ys] |= (1<<3);
				}
			}
		}
		int cur = 0, next = 1;
		for(int i=0;i<t;i++){
			int d; char c; cin >> d >> c;
			int targetDir = getDir(c);
			for(int j=0;j<d;j++){
				memset(visit[next], 0, sizeof(visit[next]));
				for(int x=0;x<=50;x++){
					for(int y=0;y<=50;y++){
						for(int dir=0;dir<4;dir++){
							if(!(visit[cur][x][y]&(1<<dir))) continue;
							if(!(mp[x][y]&(1<<dir))) continue;
							int nx = x+dx[dir], ny = y+dy[dir];
							visit[next][nx][ny] |= (1<<dir);
						}
					}
				}
				for(int x=0;x<=50;x++){
					for(int y=0;y<=50;y++){
						int nmask = 0;
						for(int dir=0;dir<4;dir++){
							if(!(visit[next][x][y]&(1<<dir))) continue;
							int mask = (15^(1<<((dir+2)%4)))&mp[x][y];
							if(j==d-1 && dir != targetDir) mask &= (1<< targetDir);
							nmask |= mask;
						}
						visit[next][x][y] = nmask;
					}
				}
				swap(cur, next);
			}
		}
		for(int x=0;x<=50;x++){
			for(int y=0;y<=50;y++){
				if(visit[cur][x][y]) cout << x << " " << y << endl;
			}
		}
	}
}
```