/*
 * e.cc: 
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>

using namespace std;

/* constant */

const int MAX_N = 50;
const int MAX_T = 100;
const int MAX_D = 10;
const int MAX_H = 50;
const int MAX_W = 50;

const int dxs[] = {1, 0, -1, 0}, dys[] = {0, 1, 0, -1}; // E,N,W,S

/* typedef */

typedef pair<int,int> pii;
typedef set<pii> spii;

struct Stat {
  int x, y, di, i, d;
  Stat() {}
  Stat(int _x, int _y, int _di, int _i, int _d):
    x(_x), y(_y), di(_di), i(_i), d(_d) {}
};

/* global variables */

bool nbrs[MAX_H + 1][MAX_W + 1][4];
bool used[MAX_H + 1][MAX_W + 1][4][MAX_T + 1][MAX_D + 1];
int ds[MAX_T + 1], dis[MAX_T + 1];

/* subroutines */

/* main */

int main() {
  int n, x0, y0, t;
  cin >> n >> x0 >> y0 >> t;

  for (int i = 0; i < n; i++) {
    int xs, ys, xe, ye;
    cin >> xs >> ys >> xe >> ye;
    if (xs == xe) {
      if (ys > ye) swap(ys, ye);
      for (int y = ys; y < ye; y++)
	nbrs[y][xs][1] = nbrs[y + 1][xs][3] = true;
    }
    else {
      if (xs > xe) swap(xs, xe);
      for (int x = xs; x < xe; x++)
	nbrs[ys][x][0] = nbrs[ys][x + 1][2] = true;
    }
  }

  for (int i = 0; i < t; i++) {
    char ch;
    cin >> ds[i] >> ch;
    switch (ch) {
    case 'E': dis[i] = 0; break;
    case 'N': dis[i] = 1; break;
    case 'W': dis[i] = 2; break;
    case 'S': dis[i] = 3; break;
    }
  }
  ds[t] = 1;
  dis[t] = -1;
  
  queue<Stat> q;
  for (int di = 0; di < 4; di++)
    if (nbrs[y0][x0][di]) {
      q.push(Stat(x0, y0, di, 0, ds[0]));
      used[y0][x0][di][0][ds[0]] = true;
    }

  spii ans;
  
  while (! q.empty()) {
    Stat u = q.front(); q.pop();

    int cdi = -1;
    if (u.d == 0) {
      cdi = dis[u.i];
      u.d = ds[++u.i];
    }

    u.d--;
    int rudi = (u.di + 2) % 4;

    for (int vdi = 0; vdi < 4; vdi++)
      if (nbrs[u.y][u.x][vdi] && vdi != rudi) {
	if (cdi >= 0 && cdi != u.di && cdi != vdi) continue;
	if (u.i >= t) {
	  ans.insert(pii(u.x, u.y));
	  continue;
	}
	int vx = u.x + dxs[vdi], vy = u.y + dys[vdi];
	if (! used[vy][vx][vdi][u.i][u.d]) {
	  q.push(Stat(vx, vy, vdi, u.i, u.d));
	  used[vy][vx][vdi][u.i][u.d] = true;
	}
      }
  }

  for (spii::iterator sit = ans.begin(); sit != ans.end(); sit++)
    printf("%d %d\n", sit->first, sit->second);
  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
/*
 * e.cc: 
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>

using namespace std;

/* constant */

const int MAX_N = 50;
const int MAX_T = 100;
const int MAX_D = 10;
const int MAX_H = 50;
const int MAX_W = 50;

const int dxs[] = {1, 0, -1, 0}, dys[] = {0, 1, 0, -1}; // E,N,W,S

/* typedef */

typedef pair<int,int> pii;
typedef set<pii> spii;

struct Stat {
  int x, y, di, i, d;
  Stat() {}
  Stat(int _x, int _y, int _di, int _i, int _d):
    x(_x), y(_y), di(_di), i(_i), d(_d) {}
};

/* global variables */

bool nbrs[MAX_H + 1][MAX_W + 1][4];
bool used[MAX_H + 1][MAX_W + 1][4][MAX_T + 1][MAX_D + 1];
int ds[MAX_T + 1], dis[MAX_T + 1];

/* subroutines */

/* main */

int main() {
  int n, x0, y0, t;
  cin >> n >> x0 >> y0 >> t;

  for (int i = 0; i < n; i++) {
    int xs, ys, xe, ye;
    cin >> xs >> ys >> xe >> ye;
    if (xs == xe) {
      if (ys > ye) swap(ys, ye);
      for (int y = ys; y < ye; y++)
	nbrs[y][xs][1] = nbrs[y + 1][xs][3] = true;
    }
    else {
      if (xs > xe) swap(xs, xe);
      for (int x = xs; x < xe; x++)
	nbrs[ys][x][0] = nbrs[ys][x + 1][2] = true;
    }
  }

  for (int i = 0; i < t; i++) {
    char ch;
    cin >> ds[i] >> ch;
    switch (ch) {
    case 'E': dis[i] = 0; break;
    case 'N': dis[i] = 1; break;
    case 'W': dis[i] = 2; break;
    case 'S': dis[i] = 3; break;
    }
  }
  ds[t] = 1;
  dis[t] = -1;
  
  queue<Stat> q;
  for (int di = 0; di < 4; di++)
    if (nbrs[y0][x0][di]) {
      q.push(Stat(x0, y0, di, 0, ds[0]));
      used[y0][x0][di][0][ds[0]] = true;
    }

  spii ans;
  
  while (! q.empty()) {
    Stat u = q.front(); q.pop();

    int cdi = -1;
    if (u.d == 0) {
      cdi = dis[u.i];
      u.d = ds[++u.i];
    }

    u.d--;
    int rudi = (u.di + 2) % 4;

    for (int vdi = 0; vdi < 4; vdi++)
      if (nbrs[u.y][u.x][vdi] && vdi != rudi) {
	if (cdi >= 0 && cdi != u.di && cdi != vdi) continue;
	if (u.i >= t) {
	  ans.insert(pii(u.x, u.y));
	  continue;
	}
	int vx = u.x + dxs[vdi], vy = u.y + dys[vdi];
	if (! used[vy][vx][vdi][u.i][u.d]) {
	  q.push(Stat(vx, vy, vdi, u.i, u.d));
	  used[vy][vx][vdi][u.i][u.d] = true;
	}
      }
  }

  for (spii::iterator sit = ans.begin(); sit != ans.end(); sit++)
    printf("%d %d\n", sit->first, sit->second);
  return 0;
}
```