#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

#define NUM 51

enum DIR{
	North,
	East,
	South,
	West,
};

int diff_x[4] = {0,1,0,-1},diff_y[4] = {1,0,-1,0};
bool can_move[NUM][NUM][4],dp[2][NUM][NUM][4];
int table[128];
DIR dir_array[4] = {North,East,South,West};

int N;

bool rangeCheck(int x,int y){

	if(x >= 0 && x < NUM && y >= 0 && y < NUM)return true;
	else{
		return false;
	}
}

int main(){

	table['N'] = 0;
	table['E'] = 1;
	table['S'] = 2;
	table['W'] = 3;

	int start_x,start_y,T;
	scanf("%d %d %d %d",&N,&start_x,&start_y,&T);

	for(int i = 0; i < NUM; i++){
		for(int k = 0; k < NUM; k++){
			for(int p = 0; p < 4; p++)can_move[i][k][p] = false;
		}
	}

	//移動可能情報の作成
	int x1,y1,x2,y2;
	for(int loop = 0; loop < N; loop++){

		scanf("%d %d %d %d",&x1,&y1,&x2,&y2);

		if(x1 == x2){ //縦の移動

			for(int y = min(y1,y2); y < max(y1,y2); y++){
				can_move[x1][y][North] = true;
				can_move[x1][y+1][South] = true;
			}

		}else{ //横の移動

			for(int x = min(x1,x2); x < max(x1,x2); x++){
				can_move[x][y1][East] = true;
				can_move[x+1][y1][West] = true;
			}
		}
	}

	int CURRENT = 0,NEXT = 1;

	for(int i = 0; i < NUM; i++){
		for(int k = 0; k < NUM; k++){
			for(int p = 0; p < 4; p++){
				dp[CURRENT][i][k][p] = false; //dp[CURRENT/NEXT][x][y][dir] = true/false
			}
		}
	}

	for(int i = 0; i < 4; i++)dp[CURRENT][start_x][start_y][i] = true;

	int dist,next_x,next_y;
	char buf[2];

	DIR dir;

	for(int loop = 0; loop < T; loop++){

		scanf("%d %s",&dist,buf);
		dir = dir_array[table[buf[0]]];

		for(int count = 0; count < dist; count++){ //合計でdist移動する

			//dp[NEXT]の初期化
			for(int i = 0; i < NUM; i++){
				for(int k = 0; k < NUM; k++){
					for(int p = 0; p < 4; p++){
						dp[NEXT][i][k][p] = false;
					}
				}
			}
			//dp[CURRENT]を走査
			for(int i = 0; i < NUM; i++){ //xのループ
				for(int k = 0; k < NUM; k++){ //yのループ
					for(int p = 0; p < 4; p++){ //今向いている方向
						if(!dp[CURRENT][i][k][p])continue;

						for(int a = 0; a < 4; a++){ //進んだ後に向く方向
							if(abs(p-a) == 2)continue; //Uターン禁止

							next_x = i+diff_x[p]; //今向いている向きに進む
							next_y = k+diff_y[p];

							if(rangeCheck(next_x,next_y) == false || can_move[i][k][p] == false
									|| can_move[next_x][next_y][a] == false)continue; //範囲外または行けないならSKIP

							if(count < dist-1){

								dp[NEXT][next_x][next_y][a] = true;

							}else{ //count == dist-1:向きを考慮する!!

								if(dir_array[p] == dir || dir_array[a] == dir){
									dp[NEXT][next_x][next_y][a] = true;
								}
							}
						}
					}
				}
			}
			swap(CURRENT,NEXT);
		}
	}

	for(int i = 0; i < NUM; i++){
		for(int k = 0; k < NUM; k++){
			for(int a = 0; a < 4; a++){
				if(dp[CURRENT][i][k][a]){
					printf("%d %d\n",i,k);
					break;
				}
			}
		}
	}

	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>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

#define NUM 51

enum DIR{
	North,
	East,
	South,
	West,
};

int diff_x[4] = {0,1,0,-1},diff_y[4] = {1,0,-1,0};
bool can_move[NUM][NUM][4],dp[2][NUM][NUM][4];
int table[128];
DIR dir_array[4] = {North,East,South,West};

int N;

bool rangeCheck(int x,int y){

	if(x >= 0 && x < NUM && y >= 0 && y < NUM)return true;
	else{
		return false;
	}
}

int main(){

	table['N'] = 0;
	table['E'] = 1;
	table['S'] = 2;
	table['W'] = 3;

	int start_x,start_y,T;
	scanf("%d %d %d %d",&N,&start_x,&start_y,&T);

	for(int i = 0; i < NUM; i++){
		for(int k = 0; k < NUM; k++){
			for(int p = 0; p < 4; p++)can_move[i][k][p] = false;
		}
	}

	//移動可能情報の作成
	int x1,y1,x2,y2;
	for(int loop = 0; loop < N; loop++){

		scanf("%d %d %d %d",&x1,&y1,&x2,&y2);

		if(x1 == x2){ //縦の移動

			for(int y = min(y1,y2); y < max(y1,y2); y++){
				can_move[x1][y][North] = true;
				can_move[x1][y+1][South] = true;
			}

		}else{ //横の移動

			for(int x = min(x1,x2); x < max(x1,x2); x++){
				can_move[x][y1][East] = true;
				can_move[x+1][y1][West] = true;
			}
		}
	}

	int CURRENT = 0,NEXT = 1;

	for(int i = 0; i < NUM; i++){
		for(int k = 0; k < NUM; k++){
			for(int p = 0; p < 4; p++){
				dp[CURRENT][i][k][p] = false; //dp[CURRENT/NEXT][x][y][dir] = true/false
			}
		}
	}

	for(int i = 0; i < 4; i++)dp[CURRENT][start_x][start_y][i] = true;

	int dist,next_x,next_y;
	char buf[2];

	DIR dir;

	for(int loop = 0; loop < T; loop++){

		scanf("%d %s",&dist,buf);
		dir = dir_array[table[buf[0]]];

		for(int count = 0; count < dist; count++){ //合計でdist移動する

			//dp[NEXT]の初期化
			for(int i = 0; i < NUM; i++){
				for(int k = 0; k < NUM; k++){
					for(int p = 0; p < 4; p++){
						dp[NEXT][i][k][p] = false;
					}
				}
			}
			//dp[CURRENT]を走査
			for(int i = 0; i < NUM; i++){ //xのループ
				for(int k = 0; k < NUM; k++){ //yのループ
					for(int p = 0; p < 4; p++){ //今向いている方向
						if(!dp[CURRENT][i][k][p])continue;

						for(int a = 0; a < 4; a++){ //進んだ後に向く方向
							if(abs(p-a) == 2)continue; //Uターン禁止

							next_x = i+diff_x[p]; //今向いている向きに進む
							next_y = k+diff_y[p];

							if(rangeCheck(next_x,next_y) == false || can_move[i][k][p] == false
									|| can_move[next_x][next_y][a] == false)continue; //範囲外または行けないならSKIP

							if(count < dist-1){

								dp[NEXT][next_x][next_y][a] = true;

							}else{ //count == dist-1:向きを考慮する!!

								if(dir_array[p] == dir || dir_array[a] == dir){
									dp[NEXT][next_x][next_y][a] = true;
								}
							}
						}
					}
				}
			}
			swap(CURRENT,NEXT);
		}
	}

	for(int i = 0; i < NUM; i++){
		for(int k = 0; k < NUM; k++){
			for(int a = 0; a < 4; a++){
				if(dp[CURRENT][i][k][a]){
					printf("%d %d\n",i,k);
					break;
				}
			}
		}
	}

	return 0;
}


```