#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define endl '\n'
#define ALL(a) (a).begin(),(a).end()
#define SZ(a) (int)((a).size())
typedef long long ll;
typedef pair<int,int> PI;

vector<int> G[100][100];

int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};

bool can[51][51][4];
bool can2[51][51][4];

int main(int argc, char *argv[])
{
  int n,x,y,t;
  cin >> n >> x >> y >> t;
  
  rep(i,n){
    int xs,ys,xe,ye;
    cin >> xs >> ys >> xe >> ye;

    int dx = (xe-xs);
    int dy = (ye-ys);
    if(dx) dx/=abs(dx);
    if(dy) dy/=abs(dy);
    int dir;
    if(dx==1) dir = 1;
    else if(dx==-1) dir = 3;
    else if(dy == 1) dir = 0;
    else dir = 2;
    
    while(xs != xe || ys != ye){
      G[xs][ys].pb(dir);
      G[xs+dx][ys+dy].pb(dir^2);
      xs += dx;
      ys += dy;
    }
  }
  
  rep(i,4)
    can[x][y][i] = 1;
  
  rep(tjj,t){
    int d;
    char c;
    cin >> d >> c;
    int cdir = string("NESW").find(c);
    //cout << cdir << endl;
    
    rep(jj,d){
      memset(can2,0,sizeof(can2));
      // cout << "time " << jj << endl;
      // rep(x,51)rep(y,51)rep(j,4)
      //   if(can[x][y][j])
      //     cout << x << " " << y << " " << j << endl;
      
      rep(x,51)rep(y,51){
        rep(j,4) if(can[x][y][j]){
          for(auto e : G[x][y]){
            if(j!=e) continue;
            int nx = x + dx[j];
            int ny = y + dy[j];
            //cout << "hoge" << endl;
            can2[nx][ny][e] = 1;
          }
        }
      }
      
      memcpy(can,can2,sizeof(can));
      

      if(jj == d-1) break;
      
      memset(can2,0,sizeof(can2));
      
      rep(x,51)rep(y,51){
        rep(j,4) if(can[x][y][j]){
          can2[x][y][j] = 1;
          for(auto e : G[x][y]){
            if((j^e)==2) continue;
            can2[x][y][e] = 1;
          }
        }
      }
      
      memcpy(can,can2,sizeof(can));
      // cout << "aft" << endl;
      // rep(x,51)rep(y,51)rep(j,4)
      //   if(can[x][y][j])
      //     cout << x << " " << y << " " << j << endl;
    }

    //cout << endl;

    memset(can2,0,sizeof(can2));
      
    rep(x,51)rep(y,51){
      rep(j,4) if(can[x][y][j]){
        if(j==cdir){
          can2[x][y][j] = 1;
          for(auto e : G[x][y]){
            if((j^e)==2) continue;
            can2[x][y][e] = 1;
          }
        }else{
          for(auto e : G[x][y]){
            if((j^e)==2) continue;
            if(e != cdir) continue;
            can2[x][y][e] = 1;
          }
        }
        continue;
        
        can2[x][y][j] = 1;
        for(auto e : G[x][y]){
          if((j^e)==2) continue;
          can2[x][y][e] = 1;
        }
      }
    }
      
    memcpy(can,can2,sizeof(can));
    
    set<PI> ans;
    rep(x,51)rep(y,51){
      rep(j,4){
        if(can[x][y][j]) ans.insert(mp(x,y));
        //else can[x][y][j] = false;
      }
    }
    
    if(tjj==t-1)
      for(auto a : ans)
        cout << a.F << " " << a.S << endl;
  }
  
  
  return 0;
}
### Prompt

Create a solution in Cpp for 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>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define endl '\n'
#define ALL(a) (a).begin(),(a).end()
#define SZ(a) (int)((a).size())
typedef long long ll;
typedef pair<int,int> PI;

vector<int> G[100][100];

int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};

bool can[51][51][4];
bool can2[51][51][4];

int main(int argc, char *argv[])
{
  int n,x,y,t;
  cin >> n >> x >> y >> t;
  
  rep(i,n){
    int xs,ys,xe,ye;
    cin >> xs >> ys >> xe >> ye;

    int dx = (xe-xs);
    int dy = (ye-ys);
    if(dx) dx/=abs(dx);
    if(dy) dy/=abs(dy);
    int dir;
    if(dx==1) dir = 1;
    else if(dx==-1) dir = 3;
    else if(dy == 1) dir = 0;
    else dir = 2;
    
    while(xs != xe || ys != ye){
      G[xs][ys].pb(dir);
      G[xs+dx][ys+dy].pb(dir^2);
      xs += dx;
      ys += dy;
    }
  }
  
  rep(i,4)
    can[x][y][i] = 1;
  
  rep(tjj,t){
    int d;
    char c;
    cin >> d >> c;
    int cdir = string("NESW").find(c);
    //cout << cdir << endl;
    
    rep(jj,d){
      memset(can2,0,sizeof(can2));
      // cout << "time " << jj << endl;
      // rep(x,51)rep(y,51)rep(j,4)
      //   if(can[x][y][j])
      //     cout << x << " " << y << " " << j << endl;
      
      rep(x,51)rep(y,51){
        rep(j,4) if(can[x][y][j]){
          for(auto e : G[x][y]){
            if(j!=e) continue;
            int nx = x + dx[j];
            int ny = y + dy[j];
            //cout << "hoge" << endl;
            can2[nx][ny][e] = 1;
          }
        }
      }
      
      memcpy(can,can2,sizeof(can));
      

      if(jj == d-1) break;
      
      memset(can2,0,sizeof(can2));
      
      rep(x,51)rep(y,51){
        rep(j,4) if(can[x][y][j]){
          can2[x][y][j] = 1;
          for(auto e : G[x][y]){
            if((j^e)==2) continue;
            can2[x][y][e] = 1;
          }
        }
      }
      
      memcpy(can,can2,sizeof(can));
      // cout << "aft" << endl;
      // rep(x,51)rep(y,51)rep(j,4)
      //   if(can[x][y][j])
      //     cout << x << " " << y << " " << j << endl;
    }

    //cout << endl;

    memset(can2,0,sizeof(can2));
      
    rep(x,51)rep(y,51){
      rep(j,4) if(can[x][y][j]){
        if(j==cdir){
          can2[x][y][j] = 1;
          for(auto e : G[x][y]){
            if((j^e)==2) continue;
            can2[x][y][e] = 1;
          }
        }else{
          for(auto e : G[x][y]){
            if((j^e)==2) continue;
            if(e != cdir) continue;
            can2[x][y][e] = 1;
          }
        }
        continue;
        
        can2[x][y][j] = 1;
        for(auto e : G[x][y]){
          if((j^e)==2) continue;
          can2[x][y][e] = 1;
        }
      }
    }
      
    memcpy(can,can2,sizeof(can));
    
    set<PI> ans;
    rep(x,51)rep(y,51){
      rep(j,4){
        if(can[x][y][j]) ans.insert(mp(x,y));
        //else can[x][y][j] = false;
      }
    }
    
    if(tjj==t-1)
      for(auto a : ans)
        cout << a.F << " " << a.S << endl;
  }
  
  
  return 0;
}
```