#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
typedef long long LL;
int n;
int sx,sy;
int t;
int ax[6001];
int ay[6001];
enum Compass{North,East,West,South};

bool dp[2][4][3001];

int p_num=0;
typedef pair<int,int>P;
map<P,int>m;

bool dp2[2][4][3001];

void update(int x,int y,int dir){
     if(m.count(P(x,y))>0)dp2[0][dir][m[{x,y}]]=true;
}
 int dx[4]={0,1,-1,0};
 int dy[4]={1,0,0,-1};
void move_one(){

  
    
     REP(i,2){
         REP(j,4){
             REP(k,3001){
                 dp2[i][j][k]=false;
             }
         }
     }
     
     REP(j,4){
        REP(k,3001){
             if(dp[0][j][k]==true){
                 REP(l,4){
                     if(j+l==3)continue;
                     update(ax[k]+dx[l],ay[k]+dy[l],l);
                 }
             }
         }
     }
     REP(j,4){
        REP(k,3001){
             if(dp[1][j][k]==true){
                 update(ax[k]+dx[j],ay[k]+dy[j],j);
             }
         }
     }
     
     REP(i,2){
         REP(j,4){
             REP(k,3001){
                 dp[i][j][k]=dp2[i][j][k];
             }
         }
     }
     

}

void cut(int dir){
   REP(i,4){
       REP(j,3001){
           if(i==dir)continue;
           if(dp[0][i][j]==false)continue;
           dp[0][i][j]=false;
           if(i+dir==3)continue;
           if(m.count({ax[j]+dx[dir],ay[j]+dy[dir]})!=0){
              dp[1][dir][j]=true;
           }
       }
   }
   REP(i,4){
       REP(j,3001){
           if(i==dir)continue;
           dp[1][i][j]=false;
       }
   }
   
}

void move(){
     int dis;
     string dir;
     cin>>dis>>dir;
     dis*=2;
     /*cout<<"before---------------"<<endl;
     REP(i,2){
         REP(j,4){
             REP(k,3001){
                 if(dp[i][j][k]){
                    cout<<ax[k]<<" "<<ay[k]<<" "<<j<<" "<<i<<endl;;
                 }
             }
         }
     }*/
     REP(i,dis){
         move_one();
     }
     
     /*cout<<"after---------------"<<endl;
     REP(i,2){
         REP(j,4){
             REP(k,3001){
                 if(dp[i][j][k]){
                    cout<<ax[k]<<" "<<ay[k]<<" "<<j<<endl;;
                 }
             }
         }
     }
     */
     if(dir=="N"){
        cut(0);
     }
     if(dir=="E"){
        cut(1);
     }
     if(dir=="W"){
        cut(2);
     }
     if(dir=="S"){
        cut(3);
     }
     
}

void show(){
     REP(i,50){
         REP(j,50){
             if(m.count({j,i})==0){
                cout<<"x";
             }else{
                cout<<"o";
             }
             if(j%5==4)cout<<" ";
         }
         cout<<endl;
         if(i%5==4)cout<<endl;
     }
}

int main(){
    cin>>n>>sx>>sy>>t;
    sx*=2;sy*=2;
    REP(i,n){
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        a*=2;
        b*=2;
        c*=2;
        d*=2;
        if(a==c){
           for(int j=min(b,d);j<=max(b,d);j++){
              // REP(k,4){
                   ax[p_num]=a;
                   ay[p_num]=j;
                   m[{a,j}]=p_num;
                   p_num++;
              // }
           }
        }else{
           for(int j=min(a,c);j<=max(a,c);j++){
              // REP(k,4){
                   ax[p_num]=j;
                   ay[p_num]=b;
                   m[{j,b}]=p_num;
                   p_num++;
              // }
           }
        }
    }
   // show();
    REP(i,2)REP(j,4)REP(k,3001)dp[i][j][k]=false;
    REP(i,4){
        dp[0][i][m[P(sx,sy)]]=true;
    }
    REP(i,t){
        move();
    }
    
    
    vector<P>v;
    REP(i,2){
        REP(j,4){
            REP(k,3001){
                if(dp[i][j][k]==true)v.push_back({ax[k],ay[k]});
            }
        }
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    //cout<<"ans-----------"<<endl;
    REP(i,v.size()){
        cout<<v[i].first/2<<" "<<v[i].second/2<<endl;
    }
    
    return(0);
}
### Prompt

Your task is to create 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;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
typedef long long LL;
int n;
int sx,sy;
int t;
int ax[6001];
int ay[6001];
enum Compass{North,East,West,South};

bool dp[2][4][3001];

int p_num=0;
typedef pair<int,int>P;
map<P,int>m;

bool dp2[2][4][3001];

void update(int x,int y,int dir){
     if(m.count(P(x,y))>0)dp2[0][dir][m[{x,y}]]=true;
}
 int dx[4]={0,1,-1,0};
 int dy[4]={1,0,0,-1};
void move_one(){

  
    
     REP(i,2){
         REP(j,4){
             REP(k,3001){
                 dp2[i][j][k]=false;
             }
         }
     }
     
     REP(j,4){
        REP(k,3001){
             if(dp[0][j][k]==true){
                 REP(l,4){
                     if(j+l==3)continue;
                     update(ax[k]+dx[l],ay[k]+dy[l],l);
                 }
             }
         }
     }
     REP(j,4){
        REP(k,3001){
             if(dp[1][j][k]==true){
                 update(ax[k]+dx[j],ay[k]+dy[j],j);
             }
         }
     }
     
     REP(i,2){
         REP(j,4){
             REP(k,3001){
                 dp[i][j][k]=dp2[i][j][k];
             }
         }
     }
     

}

void cut(int dir){
   REP(i,4){
       REP(j,3001){
           if(i==dir)continue;
           if(dp[0][i][j]==false)continue;
           dp[0][i][j]=false;
           if(i+dir==3)continue;
           if(m.count({ax[j]+dx[dir],ay[j]+dy[dir]})!=0){
              dp[1][dir][j]=true;
           }
       }
   }
   REP(i,4){
       REP(j,3001){
           if(i==dir)continue;
           dp[1][i][j]=false;
       }
   }
   
}

void move(){
     int dis;
     string dir;
     cin>>dis>>dir;
     dis*=2;
     /*cout<<"before---------------"<<endl;
     REP(i,2){
         REP(j,4){
             REP(k,3001){
                 if(dp[i][j][k]){
                    cout<<ax[k]<<" "<<ay[k]<<" "<<j<<" "<<i<<endl;;
                 }
             }
         }
     }*/
     REP(i,dis){
         move_one();
     }
     
     /*cout<<"after---------------"<<endl;
     REP(i,2){
         REP(j,4){
             REP(k,3001){
                 if(dp[i][j][k]){
                    cout<<ax[k]<<" "<<ay[k]<<" "<<j<<endl;;
                 }
             }
         }
     }
     */
     if(dir=="N"){
        cut(0);
     }
     if(dir=="E"){
        cut(1);
     }
     if(dir=="W"){
        cut(2);
     }
     if(dir=="S"){
        cut(3);
     }
     
}

void show(){
     REP(i,50){
         REP(j,50){
             if(m.count({j,i})==0){
                cout<<"x";
             }else{
                cout<<"o";
             }
             if(j%5==4)cout<<" ";
         }
         cout<<endl;
         if(i%5==4)cout<<endl;
     }
}

int main(){
    cin>>n>>sx>>sy>>t;
    sx*=2;sy*=2;
    REP(i,n){
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        a*=2;
        b*=2;
        c*=2;
        d*=2;
        if(a==c){
           for(int j=min(b,d);j<=max(b,d);j++){
              // REP(k,4){
                   ax[p_num]=a;
                   ay[p_num]=j;
                   m[{a,j}]=p_num;
                   p_num++;
              // }
           }
        }else{
           for(int j=min(a,c);j<=max(a,c);j++){
              // REP(k,4){
                   ax[p_num]=j;
                   ay[p_num]=b;
                   m[{j,b}]=p_num;
                   p_num++;
              // }
           }
        }
    }
   // show();
    REP(i,2)REP(j,4)REP(k,3001)dp[i][j][k]=false;
    REP(i,4){
        dp[0][i][m[P(sx,sy)]]=true;
    }
    REP(i,t){
        move();
    }
    
    
    vector<P>v;
    REP(i,2){
        REP(j,4){
            REP(k,3001){
                if(dp[i][j][k]==true)v.push_back({ax[k],ay[k]});
            }
        }
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    //cout<<"ans-----------"<<endl;
    REP(i,v.size()){
        cout<<v[i].first/2<<" "<<v[i].second/2<<endl;
    }
    
    return(0);
}
```