#include <bits/stdc++.h>
#define N 110
using namespace std;
typedef pair<int,int> P;
typedef pair<P,P> PP;
int n,Dis[N],Dir[N],mp[N][N];
int dx[]={0,2,0,-2};
int dy[]={2,0,-2,0};

bool checkDir(int y,int x,int dir,int ndir){
  int nx = x+dx[ndir]/2;
  int ny = y+dy[ndir]/2;
  return !((dir+2)%4==ndir||nx<0||ny<0||mp[ny][nx]==0);
}

int used[N][N][4];
set<PP> mem[N][N][4][12];
set<PP> getNx(int sy,int sx,int sdir,int d){
  if(used[sy][sx][sdir]++) return mem[sy][sx][sdir][d];
  bool D[N][N][4][12]={};
  queue<PP> Q;
  
  int nsy = 2*sy + dy[sdir];
  int nsx = 2*sx + dx[sdir];
  if(!checkDir(2*sy,2*sx,sdir,sdir)) return set<PP>();
  D[nsy][nsx][sdir][1] = 1;
  Q.push(PP(P(nsy,nsx),P(sdir,1)));
  mem[sy][sx][sdir][1].insert(PP(P(nsy/2,nsx/2),P(sdir,-1)));
  
  while(!Q.empty()){
    PP t = Q.front();Q.pop();
    int y = t.first.first;
    int x = t.first.second;
    int dir = t.second.first;
    int c = t.second.second;
    
    if(c==10)continue;
    for(int i=0;i<4;i++){
      int nx = x+dx[i];
      int ny = y+dy[i];
      if(!checkDir(y,x,dir,i)||D[ny][nx][i][c+1])continue; 
      D[ny][nx][i][c+1] = 1;
      Q.push(PP(P(ny,nx),P(i,c+1)));
      mem[sy][sx][sdir][c+1].insert(PP(P(ny/2,nx/2),P(i,-1)));
    }    
  }
  return mem[sy][sx][sdir][d];
}

set<P> bfs(int sy,int sx){
  set<P> res;
  bool D[N][N][N][4]={};
  queue<PP> Q;
  
  for(int i=0;i<4;i++)D[0][sy][sx][i] = 1,Q.push(PP(P(0,sy),P(sx,i)));
  
  while(!Q.empty()){
    PP t = Q.front();Q.pop();
    int idx = t.first.first;
    int y = t.first.second;
    int x = t.second.first;
    int dir = t.second.second;
    if(idx==n) {res.insert(P(x,y));continue;}

    set<PP> R = getNx(y,x,dir,Dis[idx]);
    for(PP r:R){
      int ny = r.first.first;
      int nx = r.first.second;
      int rdir = r.second.first;
      int ndir = Dir[idx];
      
      if(ndir == rdir)
	for(int j=0;j<4;j++){
	  if(!checkDir(2*ny,2*nx,rdir,j)||D[idx+1][ny][nx][j]) continue;
	  D[idx+1][ny][nx][j] = 1;
	  Q.push(PP(P(idx+1,ny),P(nx,j)));
	}

      if(ndir==rdir||!checkDir(2*ny,2*nx,rdir,ndir)||D[idx+1][ny][nx][ndir]) continue;
      D[idx+1][ny][nx][ndir] = 1;
      Q.push(PP(P(idx+1,ny),P(nx,ndir)));
    } 
  }
  return res;
}

int main(){
  int m,sx,sy;
  cin>>m>>sx>>sy>>n;
  
  for(int i=0,x,y,X,Y;i<m;i++){
    cin>>x>>y>>X>>Y;
    if(x>X)swap(x,X);
    if(y>Y)swap(y,Y);
    for(int i=2*y;i<=2*Y;i++)
      for(int j=2*x;j<=2*X;j++) mp[i][j] = 1;
  }

  for(int i=0;i<n;i++){
    char ch;
    cin>>Dis[i]>>ch;
    if(ch == 'N') Dir[i] = 0;
    if(ch == 'E') Dir[i] = 1;
    if(ch == 'S') Dir[i] = 2;
    if(ch == 'W') Dir[i] = 3;
  }

  set<P> ans = bfs(sy,sx);
  for(P a:ans)cout<<a.first<<" "<<a.second<<endl;
  return 0;
}
### Prompt

Generate 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 <bits/stdc++.h>
#define N 110
using namespace std;
typedef pair<int,int> P;
typedef pair<P,P> PP;
int n,Dis[N],Dir[N],mp[N][N];
int dx[]={0,2,0,-2};
int dy[]={2,0,-2,0};

bool checkDir(int y,int x,int dir,int ndir){
  int nx = x+dx[ndir]/2;
  int ny = y+dy[ndir]/2;
  return !((dir+2)%4==ndir||nx<0||ny<0||mp[ny][nx]==0);
}

int used[N][N][4];
set<PP> mem[N][N][4][12];
set<PP> getNx(int sy,int sx,int sdir,int d){
  if(used[sy][sx][sdir]++) return mem[sy][sx][sdir][d];
  bool D[N][N][4][12]={};
  queue<PP> Q;
  
  int nsy = 2*sy + dy[sdir];
  int nsx = 2*sx + dx[sdir];
  if(!checkDir(2*sy,2*sx,sdir,sdir)) return set<PP>();
  D[nsy][nsx][sdir][1] = 1;
  Q.push(PP(P(nsy,nsx),P(sdir,1)));
  mem[sy][sx][sdir][1].insert(PP(P(nsy/2,nsx/2),P(sdir,-1)));
  
  while(!Q.empty()){
    PP t = Q.front();Q.pop();
    int y = t.first.first;
    int x = t.first.second;
    int dir = t.second.first;
    int c = t.second.second;
    
    if(c==10)continue;
    for(int i=0;i<4;i++){
      int nx = x+dx[i];
      int ny = y+dy[i];
      if(!checkDir(y,x,dir,i)||D[ny][nx][i][c+1])continue; 
      D[ny][nx][i][c+1] = 1;
      Q.push(PP(P(ny,nx),P(i,c+1)));
      mem[sy][sx][sdir][c+1].insert(PP(P(ny/2,nx/2),P(i,-1)));
    }    
  }
  return mem[sy][sx][sdir][d];
}

set<P> bfs(int sy,int sx){
  set<P> res;
  bool D[N][N][N][4]={};
  queue<PP> Q;
  
  for(int i=0;i<4;i++)D[0][sy][sx][i] = 1,Q.push(PP(P(0,sy),P(sx,i)));
  
  while(!Q.empty()){
    PP t = Q.front();Q.pop();
    int idx = t.first.first;
    int y = t.first.second;
    int x = t.second.first;
    int dir = t.second.second;
    if(idx==n) {res.insert(P(x,y));continue;}

    set<PP> R = getNx(y,x,dir,Dis[idx]);
    for(PP r:R){
      int ny = r.first.first;
      int nx = r.first.second;
      int rdir = r.second.first;
      int ndir = Dir[idx];
      
      if(ndir == rdir)
	for(int j=0;j<4;j++){
	  if(!checkDir(2*ny,2*nx,rdir,j)||D[idx+1][ny][nx][j]) continue;
	  D[idx+1][ny][nx][j] = 1;
	  Q.push(PP(P(idx+1,ny),P(nx,j)));
	}

      if(ndir==rdir||!checkDir(2*ny,2*nx,rdir,ndir)||D[idx+1][ny][nx][ndir]) continue;
      D[idx+1][ny][nx][ndir] = 1;
      Q.push(PP(P(idx+1,ny),P(nx,ndir)));
    } 
  }
  return res;
}

int main(){
  int m,sx,sy;
  cin>>m>>sx>>sy>>n;
  
  for(int i=0,x,y,X,Y;i<m;i++){
    cin>>x>>y>>X>>Y;
    if(x>X)swap(x,X);
    if(y>Y)swap(y,Y);
    for(int i=2*y;i<=2*Y;i++)
      for(int j=2*x;j<=2*X;j++) mp[i][j] = 1;
  }

  for(int i=0;i<n;i++){
    char ch;
    cin>>Dis[i]>>ch;
    if(ch == 'N') Dir[i] = 0;
    if(ch == 'E') Dir[i] = 1;
    if(ch == 'S') Dir[i] = 2;
    if(ch == 'W') Dir[i] = 3;
  }

  set<P> ans = bfs(sy,sx);
  for(P a:ans)cout<<a.first<<" "<<a.second<<endl;
  return 0;
}
```