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

struct dat{
  int idx1, idx2, y, x, d;
};

bool d[101][11][51][51][4];
vector<P> G[51][51][4];
int memo[51][51][4];
int n, x_0, y_0, t, D[101];
char c[101];

void add_edge(int xs, int ys, int xe, int ye){
  if(ys==ye){
    for(int i=min(xs,xe);i<max(xs,xe);i++){
      G[ys][i][1].push_back(P(ys,i+1));
      memo[ys][i][1]=1; // E
      G[ys][i+1][3].push_back(P(ys,i));
      memo[ys][i+1][3]=1; // W
    }
  }else{
    for(int i=min(ys,ye);i<max(ys,ye);i++){
      G[i][xs][2].push_back(P(i+1,xs));
      memo[i][xs][2]=1; // S
      G[i+1][xs][0].push_back(P(i,xs));
      memo[i+1][xs][0]=1; // N
    }
  }
}

void bfs(){
  
  queue<dat> q;
  
  for(int i=0;i<4;i++) q.push(dat{0,0,y_0,x_0,i});
  
  while(!q.empty()){
    
    dat u=q.front(); q.pop();
    
    if(d[u.idx1][u.idx2][u.y][u.x][u.d]) continue;
    d[u.idx1][u.idx2][u.y][u.x][u.d]=true;

    if(u.idx1==t) continue;
    
    for(int i=0;i<G[u.y][u.x][u.d].size();i++){
      
      int ny=G[u.y][u.x][u.d][i].first;
      int nx=G[u.y][u.x][u.d][i].second;
      int nidx1, nidx2=u.idx2+1;
      
      if(nidx2==D[u.idx1]){
	int nd;
	if(c[u.idx1]=='S') nd=0;
	if(c[u.idx1]=='E') nd=1;
	if(c[u.idx1]=='N') nd=2;
	if(c[u.idx1]=='W') nd=3;
	nidx1=u.idx1+1;
	nidx2=0;
	if(u.d==nd){
	  for(int j=0;j<4;j++){
	    int nnd=(u.d+j)%4;
	    if(nnd==(u.d+2)%4) continue;
	    if(memo[ny][nx][nnd]) q.push(dat{nidx1,nidx2,ny,nx,nnd});
	  }
	}else{
	  for(int j=0;j<4;j++){
	    int nnd=(u.d+j)%4;
	    if(nnd==(u.d+2)%4) continue;
	    if(nnd!=nd) continue;
	    if(memo[ny][nx][nnd]) q.push(dat{nidx1,nidx2,ny,nx,nnd});
	  }
	}
      }else{
	nidx1=u.idx1;
	for(int j=0;j<4;j++){
	  int nd=(u.d+j)%4;
	  if(nd==(u.d+2)%4) continue;
	  if(memo[ny][nx][nd]) q.push(dat{nidx1,nidx2,ny,nx,nd});
	}
      }
      
    }
    
  }
  
  set<P> ans;
  
  for(int i=0;i<51;i++)
    for(int j=0;j<51;j++)
      for(int k=0;k<4;k++)
	if(d[t][0][i][j][k]) ans.insert(P(j,i));
  
  set<P>::iterator ite=ans.begin();
  
  while(ite!=ans.end()){
    cout<<(*ite).first<<' '<<(*ite).second<<endl;
    ite++;
  }
  
}

int main(){
  
  cin>>n>>x_0>>y_0>>t;
  
  for(int i=0;i<n;i++){
    int xs, ys, xe, ye;
    cin>>xs>>ys>>xe>>ye;
    add_edge(xs,ys,xe,ye);
  }
    
  for(int i=0;i<t;i++) cin>>D[i]>>c[i];
  
  bfs();
  
  return 0;
}
### 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<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;

struct dat{
  int idx1, idx2, y, x, d;
};

bool d[101][11][51][51][4];
vector<P> G[51][51][4];
int memo[51][51][4];
int n, x_0, y_0, t, D[101];
char c[101];

void add_edge(int xs, int ys, int xe, int ye){
  if(ys==ye){
    for(int i=min(xs,xe);i<max(xs,xe);i++){
      G[ys][i][1].push_back(P(ys,i+1));
      memo[ys][i][1]=1; // E
      G[ys][i+1][3].push_back(P(ys,i));
      memo[ys][i+1][3]=1; // W
    }
  }else{
    for(int i=min(ys,ye);i<max(ys,ye);i++){
      G[i][xs][2].push_back(P(i+1,xs));
      memo[i][xs][2]=1; // S
      G[i+1][xs][0].push_back(P(i,xs));
      memo[i+1][xs][0]=1; // N
    }
  }
}

void bfs(){
  
  queue<dat> q;
  
  for(int i=0;i<4;i++) q.push(dat{0,0,y_0,x_0,i});
  
  while(!q.empty()){
    
    dat u=q.front(); q.pop();
    
    if(d[u.idx1][u.idx2][u.y][u.x][u.d]) continue;
    d[u.idx1][u.idx2][u.y][u.x][u.d]=true;

    if(u.idx1==t) continue;
    
    for(int i=0;i<G[u.y][u.x][u.d].size();i++){
      
      int ny=G[u.y][u.x][u.d][i].first;
      int nx=G[u.y][u.x][u.d][i].second;
      int nidx1, nidx2=u.idx2+1;
      
      if(nidx2==D[u.idx1]){
	int nd;
	if(c[u.idx1]=='S') nd=0;
	if(c[u.idx1]=='E') nd=1;
	if(c[u.idx1]=='N') nd=2;
	if(c[u.idx1]=='W') nd=3;
	nidx1=u.idx1+1;
	nidx2=0;
	if(u.d==nd){
	  for(int j=0;j<4;j++){
	    int nnd=(u.d+j)%4;
	    if(nnd==(u.d+2)%4) continue;
	    if(memo[ny][nx][nnd]) q.push(dat{nidx1,nidx2,ny,nx,nnd});
	  }
	}else{
	  for(int j=0;j<4;j++){
	    int nnd=(u.d+j)%4;
	    if(nnd==(u.d+2)%4) continue;
	    if(nnd!=nd) continue;
	    if(memo[ny][nx][nnd]) q.push(dat{nidx1,nidx2,ny,nx,nnd});
	  }
	}
      }else{
	nidx1=u.idx1;
	for(int j=0;j<4;j++){
	  int nd=(u.d+j)%4;
	  if(nd==(u.d+2)%4) continue;
	  if(memo[ny][nx][nd]) q.push(dat{nidx1,nidx2,ny,nx,nd});
	}
      }
      
    }
    
  }
  
  set<P> ans;
  
  for(int i=0;i<51;i++)
    for(int j=0;j<51;j++)
      for(int k=0;k<4;k++)
	if(d[t][0][i][j][k]) ans.insert(P(j,i));
  
  set<P>::iterator ite=ans.begin();
  
  while(ite!=ans.end()){
    cout<<(*ite).first<<' '<<(*ite).second<<endl;
    ite++;
  }
  
}

int main(){
  
  cin>>n>>x_0>>y_0>>t;
  
  for(int i=0;i<n;i++){
    int xs, ys, xe, ye;
    cin>>xs>>ys>>xe>>ye;
    add_edge(xs,ys,xe,ye);
  }
    
  for(int i=0;i<t;i++) cin>>D[i]>>c[i];
  
  bfs();
  
  return 0;
}
```