#include <iostream>
#include <stdio.h>
#include <math.h>
#include <vector>
#include <utility>
#include <queue>

using namespace std;
typedef pair<int, int> P;
typedef pair<int, pair<P, int> > S;

int n, x_0, y_0, t;
int a[55][55];
int b[1005];
int sum = 0;
bool used[1005][55][55][4];
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

int get(char c)
{
  if(c == 'E') return 0;
  if(c == 'N') return 1;
  if(c == 'W') return 2;
  if(c == 'S') return 3;
  return -1;
}

void bfs()
{
  queue<S> Q;
  for(int i = 0; i < 4; i++){
    if(a[x_0][y_0] & (1<<i)){
      used[0][x_0][y_0][i] = true;
      Q.push(make_pair(0, make_pair(make_pair(x_0, y_0), i)));
    }
  }

  int t, x, y, d;
  while(Q.size()){
    t = Q.front().first;
    x = Q.front().second.first.first, y = Q.front().second.first.second;
    d = Q.front().second.second;
    Q.pop();
    //if((a[x][y] & (1<<d)) == 0) continue;
    int nx = x + dx[d], ny = y + dy[d];
    if(t == sum) continue;
    for(int i = 0; i < 4; i++){
      if((i+2)%4 == d) continue;
      if((a[nx][ny] & (1<<i))){
        if(used[t+1][nx][ny][i]) continue;
        if(b[t+1] != -1 && d != b[t+1] && i != b[t+1]) continue;
        used[t+1][nx][ny][i] = true;
        Q.push(make_pair(t+1, make_pair(make_pair(nx, ny), i)));
      }
    }
  }
}

int main(void)
{
  cin >> n >> x_0 >> y_0 >> t;
  int sx, sy, tx, ty;
  for(int i = 1; i <= n; i++){
    cin >> sx >> sy >> tx >> ty;
    if(sx == tx){
      if(sy > ty) swap(sy, ty);
      for(int y = sy; y <= ty; y++){
        if(y != sy) a[sx][y] |= 8;
        if(y != ty) a[sx][y] |= 2;
      }
    }
    else{
      if(sx > tx) swap(sx, tx);
      for(int x = sx; x <= tx; x++){
        if(x != sx) a[x][sy] |= 4;
        if(x != tx) a[x][sy] |= 1;
      }
    }
  }
  for(int i = 0; i < 1005; i++) b[i] = -1;
  int d; char c;
  for(int i = 1; i <= t; i++){
    cin >> d >> c;
    sum += d;
    b[sum] = get(c);
  }

  bfs();

  for(int i = 0; i <= 50; i++){
    for(int j = 0; j <= 50; j++){
      for(int k = 0; k < 4; k++){
        if(used[sum][i][j][k]){
          cout << i << " " << j << endl;
          break;
        }
      }
    }
  }

  return 0;
}


### Prompt

Please formulate 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 <iostream>
#include <stdio.h>
#include <math.h>
#include <vector>
#include <utility>
#include <queue>

using namespace std;
typedef pair<int, int> P;
typedef pair<int, pair<P, int> > S;

int n, x_0, y_0, t;
int a[55][55];
int b[1005];
int sum = 0;
bool used[1005][55][55][4];
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

int get(char c)
{
  if(c == 'E') return 0;
  if(c == 'N') return 1;
  if(c == 'W') return 2;
  if(c == 'S') return 3;
  return -1;
}

void bfs()
{
  queue<S> Q;
  for(int i = 0; i < 4; i++){
    if(a[x_0][y_0] & (1<<i)){
      used[0][x_0][y_0][i] = true;
      Q.push(make_pair(0, make_pair(make_pair(x_0, y_0), i)));
    }
  }

  int t, x, y, d;
  while(Q.size()){
    t = Q.front().first;
    x = Q.front().second.first.first, y = Q.front().second.first.second;
    d = Q.front().second.second;
    Q.pop();
    //if((a[x][y] & (1<<d)) == 0) continue;
    int nx = x + dx[d], ny = y + dy[d];
    if(t == sum) continue;
    for(int i = 0; i < 4; i++){
      if((i+2)%4 == d) continue;
      if((a[nx][ny] & (1<<i))){
        if(used[t+1][nx][ny][i]) continue;
        if(b[t+1] != -1 && d != b[t+1] && i != b[t+1]) continue;
        used[t+1][nx][ny][i] = true;
        Q.push(make_pair(t+1, make_pair(make_pair(nx, ny), i)));
      }
    }
  }
}

int main(void)
{
  cin >> n >> x_0 >> y_0 >> t;
  int sx, sy, tx, ty;
  for(int i = 1; i <= n; i++){
    cin >> sx >> sy >> tx >> ty;
    if(sx == tx){
      if(sy > ty) swap(sy, ty);
      for(int y = sy; y <= ty; y++){
        if(y != sy) a[sx][y] |= 8;
        if(y != ty) a[sx][y] |= 2;
      }
    }
    else{
      if(sx > tx) swap(sx, tx);
      for(int x = sx; x <= tx; x++){
        if(x != sx) a[x][sy] |= 4;
        if(x != tx) a[x][sy] |= 1;
      }
    }
  }
  for(int i = 0; i < 1005; i++) b[i] = -1;
  int d; char c;
  for(int i = 1; i <= t; i++){
    cin >> d >> c;
    sum += d;
    b[sum] = get(c);
  }

  bfs();

  for(int i = 0; i <= 50; i++){
    for(int j = 0; j <= 50; j++){
      for(int k = 0; k < 4; k++){
        if(used[sum][i][j][k]){
          cout << i << " " << j << endl;
          break;
        }
      }
    }
  }

  return 0;
}


```