#include<bits/stdc++.h>
using namespace std;

const int SIZE=101;
using Field=array<array<int,SIZE>,SIZE>;
map<char,int> dmap={{'N',0},{'E',1},{'S',2},{'W',3}};
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
Field create(int v=0){
    Field res;
    for(int i=0;i<SIZE;i++) fill(res[i].begin(),res[i].end(),v);
    return res;
}
int main(){
    int n,t,x0,y0;
    cin>>n>>x0>>y0>>t;
    x0*=2,y0*=2;
    Field f=create();
    for(int i=0;i<n;i++){
        int xs,ys,xe,ye;
        cin>>xs>>ys>>xe>>ye;
        xs*=2,ys*=2,xe*=2,ye*=2;
        if(xs>xe) swap(xs,xe);
        if(ys>ye) swap(ys,ye);
        for(int x=xs;x<=xe;x++){
            for(int y=ys;y<=ye;y++){
                f[x][y]=1;
            }
        }
    }
    vector<int> d(t);
    vector<int> c(t);
    for(int i=0;i<t;i++){
        char tmp;
        cin>>d[i]>>tmp;
        d[i]=d[i]*2;
        c[i]=dmap[tmp];
    }

    vector<Field> flag(4,create());
    vector<Field> mustGO(4,create(1));
    for(int i=0;i<4;i++) flag[i][x0][y0]=true;
    auto isRange=[](int x,int y){
        return 0<=x && x<SIZE && 0<=y && y<SIZE;
    };
    auto move=[&](){
        vector<Field> nex(4,create());
        vector<Field> nexm(4,create(1));
        for(int dir=0;dir<4;dir++){
            for(int i=0;i<SIZE;i++){
                for(int j=0;j<SIZE;j++){
                    if(!flag[dir][i][j]) continue;
                    for(int td=0;td<4;td++){
                        if(mustGO[dir][i][j] && dir!=td) continue;
                        if((td+2)%4==dir) continue;
                        int tox=i+dx[td],toy=j+dy[td];
                        if(isRange(tox,toy) && f[tox][toy]){
                            nex[td][tox][toy]=true;
                            nexm[td][tox][toy]=false;
                        }
                    }
                }
            }
        }
        flag=nex;
        mustGO=nexm;
    };
    auto judge=[&](int i,int j,char dir){
        int tox=i+dx[dir],toy=j+dy[dir];
        return flag[dir][i][j] || isRange(tox,toy) && (flag[(dir+1)%4][i][j] || flag[(dir+3)%4][i][j]) && f[tox][toy];
    };
    auto flesh=[&](int dir){
        for(int i=0;i<SIZE;i++){
            for(int j=0;j<SIZE;j++){
                if(flag[dir][i][j]){
                    for(int k=0;k<4;k++) flag[k][i][j]=false;
                    flag[dir][i][j]=true;
                }
                else if(judge(i,j,dir)){
                    for(int k=0;k<4;k++) flag[k][i][j]=false;
                    flag[dir][i][j]=true;
                    mustGO[dir][i][j]=true;
                }
                else{
                    for(int k=0;k<4;k++) flag[k][i][j]=false;
                }
            }
        }
    };
    for(int i=0;i<t;i++){
        for(int j=0;j<d[i];j++){
            move();
        }
        flesh(c[i]);
    }
    for(int ix=0;ix<SIZE;ix++){
        for(int j=0;j<SIZE;j++){
            if(flag[c.back()][ix][j]) cout<<ix/2<<" "<<j/2<<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;

const int SIZE=101;
using Field=array<array<int,SIZE>,SIZE>;
map<char,int> dmap={{'N',0},{'E',1},{'S',2},{'W',3}};
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
Field create(int v=0){
    Field res;
    for(int i=0;i<SIZE;i++) fill(res[i].begin(),res[i].end(),v);
    return res;
}
int main(){
    int n,t,x0,y0;
    cin>>n>>x0>>y0>>t;
    x0*=2,y0*=2;
    Field f=create();
    for(int i=0;i<n;i++){
        int xs,ys,xe,ye;
        cin>>xs>>ys>>xe>>ye;
        xs*=2,ys*=2,xe*=2,ye*=2;
        if(xs>xe) swap(xs,xe);
        if(ys>ye) swap(ys,ye);
        for(int x=xs;x<=xe;x++){
            for(int y=ys;y<=ye;y++){
                f[x][y]=1;
            }
        }
    }
    vector<int> d(t);
    vector<int> c(t);
    for(int i=0;i<t;i++){
        char tmp;
        cin>>d[i]>>tmp;
        d[i]=d[i]*2;
        c[i]=dmap[tmp];
    }

    vector<Field> flag(4,create());
    vector<Field> mustGO(4,create(1));
    for(int i=0;i<4;i++) flag[i][x0][y0]=true;
    auto isRange=[](int x,int y){
        return 0<=x && x<SIZE && 0<=y && y<SIZE;
    };
    auto move=[&](){
        vector<Field> nex(4,create());
        vector<Field> nexm(4,create(1));
        for(int dir=0;dir<4;dir++){
            for(int i=0;i<SIZE;i++){
                for(int j=0;j<SIZE;j++){
                    if(!flag[dir][i][j]) continue;
                    for(int td=0;td<4;td++){
                        if(mustGO[dir][i][j] && dir!=td) continue;
                        if((td+2)%4==dir) continue;
                        int tox=i+dx[td],toy=j+dy[td];
                        if(isRange(tox,toy) && f[tox][toy]){
                            nex[td][tox][toy]=true;
                            nexm[td][tox][toy]=false;
                        }
                    }
                }
            }
        }
        flag=nex;
        mustGO=nexm;
    };
    auto judge=[&](int i,int j,char dir){
        int tox=i+dx[dir],toy=j+dy[dir];
        return flag[dir][i][j] || isRange(tox,toy) && (flag[(dir+1)%4][i][j] || flag[(dir+3)%4][i][j]) && f[tox][toy];
    };
    auto flesh=[&](int dir){
        for(int i=0;i<SIZE;i++){
            for(int j=0;j<SIZE;j++){
                if(flag[dir][i][j]){
                    for(int k=0;k<4;k++) flag[k][i][j]=false;
                    flag[dir][i][j]=true;
                }
                else if(judge(i,j,dir)){
                    for(int k=0;k<4;k++) flag[k][i][j]=false;
                    flag[dir][i][j]=true;
                    mustGO[dir][i][j]=true;
                }
                else{
                    for(int k=0;k<4;k++) flag[k][i][j]=false;
                }
            }
        }
    };
    for(int i=0;i<t;i++){
        for(int j=0;j<d[i];j++){
            move();
        }
        flesh(c[i]);
    }
    for(int ix=0;ix<SIZE;ix++){
        for(int j=0;j<SIZE;j++){
            if(flag[c.back()][ix][j]) cout<<ix/2<<" "<<j/2<<endl;
        }
    }
    
    
    
    return 0;
}

```