#include <bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef pair<int,int>P;
int dp[1111][55][55][4],n,t,x0,y01,T,D[11111];
int A[55][55][4];
int dx[]={0,1,0,-1};
int dy[]={-1,0,1,0};
set<P>ST;
int main(){
    memset(D,-1,sizeof(D));
    cin>>n>>x0>>y01>>t;
    r(i,n){
        int x,y,gx,gy,d,tx,ty;
        cin>>x>>y>>gx>>gy;tx=x,ty=y;
        if(x==gx){
            if(y<gy)d=2;
            else d=0;
        }
        if(y==gy){
            if(x<gx)d=1;
            else d=3;
        }
        while(!(x==gx&&y==gy)){
            A[x][y][d]=1;
            x+=dx[d];
            y+=dy[d];
        }
        d=(d+2)%4;
        while(!(x==tx&&y==ty)){
            A[x][y][d]=1;
            x+=dx[d];
            y+=dy[d];
        }
    }
    r(i,4)dp[0][x0][y01][i]=1;
    r(i,t){
        int d;
        char c;
        cin>>d>>c;
        T+=d;
        if(c=='N')D[T]=2;
        if(c=='E')D[T]=1;
        if(c=='S')D[T]=0;
        if(c=='W')D[T]=3;
    }
    r(i,T){
        r(X,55){
            r(Y,55){
                r(k,4){
                    if(!dp[i][X][Y][k])continue;
                    r(l,4){
                        if(!A[X][Y][l])continue;
                        if(l==(k+2)%4)continue;
                        if(D[i]==-1){
                            dp[i+1][X+dx[l]][Y+dy[l]][l]=1;
                        }
                        else{
                            if(l!=D[i]&&k!=D[i])continue;
                            dp[i+1][X+dx[l]][Y+dy[l]][l]=1;
                        }
                    }
                }
            }
        }
        if(i==T-1){
            r(X,55){
                r(Y,55){
                    r(k,4){
                        //cout<<X<<' '<<Y<<' '<<k<<endl;
                        if(!dp[T][X][Y][k])continue;
                        //cout<<X<<' '<<Y<<' '<<k<<endl;
                        if(k==D[T]||(A[X][Y][D[T]]&&k!=(D[T]+2)%4)){
                            cout<<X<<' '<<Y<<endl;
                            break;
                        }
                    }
                }
            }
        }
    }
}

### Prompt

Please provide a cpp coded solution to the problem described below:

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 r(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef pair<int,int>P;
int dp[1111][55][55][4],n,t,x0,y01,T,D[11111];
int A[55][55][4];
int dx[]={0,1,0,-1};
int dy[]={-1,0,1,0};
set<P>ST;
int main(){
    memset(D,-1,sizeof(D));
    cin>>n>>x0>>y01>>t;
    r(i,n){
        int x,y,gx,gy,d,tx,ty;
        cin>>x>>y>>gx>>gy;tx=x,ty=y;
        if(x==gx){
            if(y<gy)d=2;
            else d=0;
        }
        if(y==gy){
            if(x<gx)d=1;
            else d=3;
        }
        while(!(x==gx&&y==gy)){
            A[x][y][d]=1;
            x+=dx[d];
            y+=dy[d];
        }
        d=(d+2)%4;
        while(!(x==tx&&y==ty)){
            A[x][y][d]=1;
            x+=dx[d];
            y+=dy[d];
        }
    }
    r(i,4)dp[0][x0][y01][i]=1;
    r(i,t){
        int d;
        char c;
        cin>>d>>c;
        T+=d;
        if(c=='N')D[T]=2;
        if(c=='E')D[T]=1;
        if(c=='S')D[T]=0;
        if(c=='W')D[T]=3;
    }
    r(i,T){
        r(X,55){
            r(Y,55){
                r(k,4){
                    if(!dp[i][X][Y][k])continue;
                    r(l,4){
                        if(!A[X][Y][l])continue;
                        if(l==(k+2)%4)continue;
                        if(D[i]==-1){
                            dp[i+1][X+dx[l]][Y+dy[l]][l]=1;
                        }
                        else{
                            if(l!=D[i]&&k!=D[i])continue;
                            dp[i+1][X+dx[l]][Y+dy[l]][l]=1;
                        }
                    }
                }
            }
        }
        if(i==T-1){
            r(X,55){
                r(Y,55){
                    r(k,4){
                        //cout<<X<<' '<<Y<<' '<<k<<endl;
                        if(!dp[T][X][Y][k])continue;
                        //cout<<X<<' '<<Y<<' '<<k<<endl;
                        if(k==D[T]||(A[X][Y][D[T]]&&k!=(D[T]+2)%4)){
                            cout<<X<<' '<<Y<<endl;
                            break;
                        }
                    }
                }
            }
        }
    }
}

```