#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;

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

string str="NESW";
int change(char ch){
  for(int i=0;i<4;i++)
    if(ch==str[i])return i;
  return 0;
}

int n,m,sx,sy;
int ax,ay,bx,by,d,e,E;
bool t[51][51][4];
bool f[51][51][4];
bool nf[51][51][4];

void solve(bool flg){
  memset(nf,0,sizeof(nf));
  
  for(int x=0;x<=50;x++){
    for(int y=0;y<=50;y++){
      for(int prev=0;prev<4;prev++){
        if(!f[x][y][prev])continue;        
        for(int dir=0;dir<4;dir++){
          if(prev==(dir+2)%4)continue;
          if(!t[x][y][dir])continue;
          if(flg&&prev!=E&&dir!=E)continue;
          int nx=x+dx[dir],ny=y+dy[dir];
          nf[nx][ny][dir]=true;
        }
      }
    }
  }
  
  for(int x=0;x<=50;x++)
    for(int y=0;y<=50;y++)
      for(int prev=0;prev<4;prev++)
        f[x][y][prev]=nf[x][y][prev];
}

int main(){
  cin>>n>>sx>>sy>>m;
  for(int i=0;i<n;i++){
    cin>>ax>>ay>>bx>>by;
    if(ax>bx)swap(ax,bx);
    if(ay>by)swap(ay,by);
    if(ax==bx){
      for(int y=ay;y<=by;y++){
        t[ax][y][0]=(y<by);
        t[ax][y][2]=(y>ay);
      }
    }else{
      for(int x=ax;x<=bx;x++){
        t[x][ay][1]=(x<bx);
        t[x][ay][3]=(x>ax);
      }
    }
  }
  
  for(int i=0;i<4;i++)
    if(t[sx][sy][(i+2)%4])
      f[sx][sy][i]=true;
  
  char ch='N';
  e=-1;
  for(int i=0;i<m;i++){
    cin>>d>>ch;
    E=e;
    e=change(ch);
    for(int j=0;j<d;j++){
      solve(i>0&&j==0);
    }
  }

  vector<P> ans;  
  e=change(ch);
  for(int x=0;x<=50;x++){
    for(int y=0;y<=50;y++){
      bool flg=false;
      for(int z=0;z<4;z++)
        if(f[x][y][z])
          if(z==e||(t[x][y][e]&&(z+2)%4!=e))
            flg=true;
      if(flg)ans.push_back(P(x,y));
    }
  }

  sort(ans.begin(),ans.end());
  for(int i=0;i<(int)ans.size();i++){
    cout<<ans[i].first<<' '<<ans[i].second<<endl;
  }
  return 0;
}
### Prompt

In CPP, your task is to solve 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;
typedef pair<int,int> P;

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

string str="NESW";
int change(char ch){
  for(int i=0;i<4;i++)
    if(ch==str[i])return i;
  return 0;
}

int n,m,sx,sy;
int ax,ay,bx,by,d,e,E;
bool t[51][51][4];
bool f[51][51][4];
bool nf[51][51][4];

void solve(bool flg){
  memset(nf,0,sizeof(nf));
  
  for(int x=0;x<=50;x++){
    for(int y=0;y<=50;y++){
      for(int prev=0;prev<4;prev++){
        if(!f[x][y][prev])continue;        
        for(int dir=0;dir<4;dir++){
          if(prev==(dir+2)%4)continue;
          if(!t[x][y][dir])continue;
          if(flg&&prev!=E&&dir!=E)continue;
          int nx=x+dx[dir],ny=y+dy[dir];
          nf[nx][ny][dir]=true;
        }
      }
    }
  }
  
  for(int x=0;x<=50;x++)
    for(int y=0;y<=50;y++)
      for(int prev=0;prev<4;prev++)
        f[x][y][prev]=nf[x][y][prev];
}

int main(){
  cin>>n>>sx>>sy>>m;
  for(int i=0;i<n;i++){
    cin>>ax>>ay>>bx>>by;
    if(ax>bx)swap(ax,bx);
    if(ay>by)swap(ay,by);
    if(ax==bx){
      for(int y=ay;y<=by;y++){
        t[ax][y][0]=(y<by);
        t[ax][y][2]=(y>ay);
      }
    }else{
      for(int x=ax;x<=bx;x++){
        t[x][ay][1]=(x<bx);
        t[x][ay][3]=(x>ax);
      }
    }
  }
  
  for(int i=0;i<4;i++)
    if(t[sx][sy][(i+2)%4])
      f[sx][sy][i]=true;
  
  char ch='N';
  e=-1;
  for(int i=0;i<m;i++){
    cin>>d>>ch;
    E=e;
    e=change(ch);
    for(int j=0;j<d;j++){
      solve(i>0&&j==0);
    }
  }

  vector<P> ans;  
  e=change(ch);
  for(int x=0;x<=50;x++){
    for(int y=0;y<=50;y++){
      bool flg=false;
      for(int z=0;z<4;z++)
        if(f[x][y][z])
          if(z==e||(t[x][y][e]&&(z+2)%4!=e))
            flg=true;
      if(flg)ans.push_back(P(x,y));
    }
  }

  sort(ans.begin(),ans.end());
  for(int i=0;i<(int)ans.size();i++){
    cout<<ans[i].first<<' '<<ans[i].second<<endl;
  }
  return 0;
}
```