#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <utility>
#include <map>

enum Dir {
  NORTH, WEST, SOUTH, EAST
};
const size_t dx[]={0, size_t(-1), 0, 1};
const size_t dy[]={1, 0, size_t(-1), 0};

template <class Graph>
void add_edge(Graph &g, size_t xs, size_t ys, size_t xe, size_t ye) {
  if (xs == xe) {
    if (ys > ye)
      std::swap(ys, ye);

    for (size_t y=ys; y<ye; ++y)
      g[xs][y][NORTH] = true;
    for (size_t y=ys+1; y<=ye; ++y)
      g[xs][y][SOUTH] = true;
  } else {
    if (xs > xe)
      std::swap(xs, xe);

    for (size_t x=xs; x<xe; ++x)
      g[x][ys][EAST] = true;
    for (size_t x=xs+1; x<=xe; ++x)
      g[x][ys][WEST] = true;
  }
}

struct Car {
  size_t step, x, y;
  Dir d;
  Car(size_t s, size_t x, size_t y, Dir d): step(s), x(x), y(y), d(d) {}
};

int main() {
  size_t n, x0, y0, t;
  scanf("%zu %zu %zu %zu", &n, &x0, &y0, &t);

  std::vector<std::vector<std::vector<bool>>> g(
      51, std::vector<std::vector<bool>>(
        51, std::vector<bool>(4)));

  for (size_t i=0; i<n; ++i) {
    size_t xs, ys, xe, ye;
    scanf("%zu %zu %zu %zu", &xs, &ys, &xe, &ye);
    add_edge(g, xs, ys, xe, ye);
  }

  std::map<int, Dir> dir;
  std::map<char, Dir> c2d;
  c2d['N'] = NORTH;
  c2d['E'] = EAST;
  c2d['W'] = WEST;
  c2d['S'] = SOUTH;
  size_t dd=0;
  for (size_t i=0; i<t; ++i) {
    size_t d;
    char c;
    scanf("%zu %c", &d, &c);
    dd += d;
    dir[dd] = c2d[c];
  }

  std::vector<std::vector<std::vector<std::vector<int>>>> dp(
      dd+1, std::vector<std::vector<std::vector<int>>>(
        51, std::vector<std::vector<int>>(
          51, std::vector<int>(4, -1))));

  std::queue<Car> q;
  for (int i=0; i<4; ++i) {
    q.emplace(0, x0, y0, Dir(i));
    dp[0][x0][y0][i] = 1;
  }
  while (!q.empty()) {
    Car car=q.front();
    size_t s=car.step, x=car.x, y=car.y;
    Dir d=car.d;
    q.pop();
    // fprintf(stderr, "%zu: (%zu, %zu), %c\n", s, x, y, "NWSE"[size_t(d)]);

    for (size_t k=0; k<4; ++k) {
      size_t nx=x+dx[k], ny=y+dy[k];

      if (!(nx <= 50 && ny <= 50)) continue;
      if (!g[x][y][k]) continue;
      if ((d^2) == Dir(k)) continue;  // U-turn
      
      if (dir.find(car.step) != dir.end()) {
        // found
        if (d != dir[car.step] && Dir(k) != dir[car.step])
          continue;
      }
      if (s <= dd) {
        dp[s][x][y][d] = 1;
      }

      if (s+1 <= dd && dp[s+1][nx][ny][k] < 0) {
        q.emplace(s+1, nx, ny, Dir(k));
        dp[s+1][nx][ny][k] = 1;
      } else if (s == dd) {
        // fprintf(stderr, "%zu: (%zu, %zu), %c\n", s, x, y, "NWSE"[k]);
        dp[s][x][y][k] = 1;
      }
    }
  }

  for (size_t x=0; x<=50; ++x)
    for (size_t y=0; y<=50; ++y)
      if (dp[dd][x][y][dir[dd]] > 0)
        printf("%zu %zu\n", x, y);
}


### 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 <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <utility>
#include <map>

enum Dir {
  NORTH, WEST, SOUTH, EAST
};
const size_t dx[]={0, size_t(-1), 0, 1};
const size_t dy[]={1, 0, size_t(-1), 0};

template <class Graph>
void add_edge(Graph &g, size_t xs, size_t ys, size_t xe, size_t ye) {
  if (xs == xe) {
    if (ys > ye)
      std::swap(ys, ye);

    for (size_t y=ys; y<ye; ++y)
      g[xs][y][NORTH] = true;
    for (size_t y=ys+1; y<=ye; ++y)
      g[xs][y][SOUTH] = true;
  } else {
    if (xs > xe)
      std::swap(xs, xe);

    for (size_t x=xs; x<xe; ++x)
      g[x][ys][EAST] = true;
    for (size_t x=xs+1; x<=xe; ++x)
      g[x][ys][WEST] = true;
  }
}

struct Car {
  size_t step, x, y;
  Dir d;
  Car(size_t s, size_t x, size_t y, Dir d): step(s), x(x), y(y), d(d) {}
};

int main() {
  size_t n, x0, y0, t;
  scanf("%zu %zu %zu %zu", &n, &x0, &y0, &t);

  std::vector<std::vector<std::vector<bool>>> g(
      51, std::vector<std::vector<bool>>(
        51, std::vector<bool>(4)));

  for (size_t i=0; i<n; ++i) {
    size_t xs, ys, xe, ye;
    scanf("%zu %zu %zu %zu", &xs, &ys, &xe, &ye);
    add_edge(g, xs, ys, xe, ye);
  }

  std::map<int, Dir> dir;
  std::map<char, Dir> c2d;
  c2d['N'] = NORTH;
  c2d['E'] = EAST;
  c2d['W'] = WEST;
  c2d['S'] = SOUTH;
  size_t dd=0;
  for (size_t i=0; i<t; ++i) {
    size_t d;
    char c;
    scanf("%zu %c", &d, &c);
    dd += d;
    dir[dd] = c2d[c];
  }

  std::vector<std::vector<std::vector<std::vector<int>>>> dp(
      dd+1, std::vector<std::vector<std::vector<int>>>(
        51, std::vector<std::vector<int>>(
          51, std::vector<int>(4, -1))));

  std::queue<Car> q;
  for (int i=0; i<4; ++i) {
    q.emplace(0, x0, y0, Dir(i));
    dp[0][x0][y0][i] = 1;
  }
  while (!q.empty()) {
    Car car=q.front();
    size_t s=car.step, x=car.x, y=car.y;
    Dir d=car.d;
    q.pop();
    // fprintf(stderr, "%zu: (%zu, %zu), %c\n", s, x, y, "NWSE"[size_t(d)]);

    for (size_t k=0; k<4; ++k) {
      size_t nx=x+dx[k], ny=y+dy[k];

      if (!(nx <= 50 && ny <= 50)) continue;
      if (!g[x][y][k]) continue;
      if ((d^2) == Dir(k)) continue;  // U-turn
      
      if (dir.find(car.step) != dir.end()) {
        // found
        if (d != dir[car.step] && Dir(k) != dir[car.step])
          continue;
      }
      if (s <= dd) {
        dp[s][x][y][d] = 1;
      }

      if (s+1 <= dd && dp[s+1][nx][ny][k] < 0) {
        q.emplace(s+1, nx, ny, Dir(k));
        dp[s+1][nx][ny][k] = 1;
      } else if (s == dd) {
        // fprintf(stderr, "%zu: (%zu, %zu), %c\n", s, x, y, "NWSE"[k]);
        dp[s][x][y][k] = 1;
      }
    }
  }

  for (size_t x=0; x<=50; ++x)
    for (size_t y=0; y<=50; ++y)
      if (dp[dd][x][y][dir[dd]] > 0)
        printf("%zu %zu\n", x, y);
}


```