#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <string>
#include <vector>
#include <cstdio>
#include <queue>
#define  T 200
#define  N 100
using namespace std;
struct Point {
       int x, y, dist, dir;     
       Point () {}
       Point (int a,int b,int c,int d): x(a), y(b), dist(c), dir(d) {}
       bool operator<(const Point &t) const { return (t.x != x) ? x<t.x : y<t.y; }
} u;
typedef pair<int,int> pii;
vector <Point> candi;
vector <pii> ans;
int dx[] = { 0, 1, 0,-1}, dy[] = { 1, 0,-1, 0};
int d[T], p[T], f[N][N][4]; 
bool visit[N][N][16][4];
void simulate (int dist,int edir) {
     queue <Point> que;
     for (int i=0;i<candi.size();++i)
         if (!candi[i].dist)
            que.push ( candi[i] );
     for (int i=0;i<candi.size();++i)
         if (candi[i].dist)
            que.push ( candi[i] );
     candi.clear();
     memset (visit,0,sizeof(visit));
     while ( !que.empty() ) {
         u = que.front();
         que.pop();
         if ( visit[u.x][u.y][u.dist][u.dir] ) 
            continue;
         visit[u.x][u.y][u.dist][u.dir] = 1;
         if ( u.dist == dist && u.dir == edir ) {
            candi.push_back ( Point(u.x,u.y,0,edir) );
            continue;
         }
         for (int i=0;i<4;++i) {
             if ( i == (u.dir+2)%4 || !f[u.x][u.y][i] ) continue;
             int nx = u.x+dx[i], ny = u.y+dy[i];
             if (nx<0 || ny<0 || nx>=N || ny>=N ) continue;
             if ( u.dist == dist ) {  
                if ( i == edir )
                   candi.push_back ( Point(nx,ny,1,edir) );
                continue;  
             }
             que.push ( Point(nx,ny,u.dist+1,i) );
         }
     }
}
void solve (int sx,int sy,int n,int t) {
     candi.clear();
     candi.push_back ( Point(sx,sy,0,0) );
     candi.push_back ( Point(sx,sy,0,2) );
     for (int i=0;i<t;++i)
         simulate (d[i],p[i]);
     ans.clear();
     for (int i=0;i<candi.size();++i)
         if (candi[i].dist) 
            ans.push_back ( make_pair(candi[i].x-dx[candi[i].dir],candi[i].y-dy[candi[i].dir]) );    
         else 
            ans.push_back ( make_pair(candi[i].x,candi[i].y) );
     sort (ans.begin(),ans.end());
     ans.erase ( unique( ans.begin(),ans.end() ),ans.end() );
     for (int i=0;i<ans.size();++i)
         cout<<ans[i].first<<" "<<ans[i].second<<endl;    
}
int main(void) {
    cin.tie(0);
    cin.sync_with_stdio(0);
    int x1, x2, y1, y2, n, t, sx, sy;
    char c;
    while ( cin>>n>>sx>>sy>>t ) {
          memset (f,0,sizeof(f));
          for (int i=0;i<n;++i) {
              cin>>x1>>y1>>x2>>y2;
              if (x1 == x2) {
                 for (int i=min(y1,y2);i<max(y1,y2);++i)
                     f[x1][i][0] = f[x1][i+1][2] = 1;
              }
              if (y1 == y2) {
                 for (int i=min(x1,x2);i<max(x1,x2);++i)
                     f[i][y1][1] = f[i+1][y1][3] = 1;       
              }
          }
          const string dir = "NESW";
          for (int i=0;i<t;++i) {
              cin>>d[i]>>c;
              p[i] = dir.find(c);
          }
          solve (sx,sy,n,t);          
    }
    return 0;    
}
### Prompt

Construct a Cpp code solution to the problem outlined:

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 <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <string>
#include <vector>
#include <cstdio>
#include <queue>
#define  T 200
#define  N 100
using namespace std;
struct Point {
       int x, y, dist, dir;     
       Point () {}
       Point (int a,int b,int c,int d): x(a), y(b), dist(c), dir(d) {}
       bool operator<(const Point &t) const { return (t.x != x) ? x<t.x : y<t.y; }
} u;
typedef pair<int,int> pii;
vector <Point> candi;
vector <pii> ans;
int dx[] = { 0, 1, 0,-1}, dy[] = { 1, 0,-1, 0};
int d[T], p[T], f[N][N][4]; 
bool visit[N][N][16][4];
void simulate (int dist,int edir) {
     queue <Point> que;
     for (int i=0;i<candi.size();++i)
         if (!candi[i].dist)
            que.push ( candi[i] );
     for (int i=0;i<candi.size();++i)
         if (candi[i].dist)
            que.push ( candi[i] );
     candi.clear();
     memset (visit,0,sizeof(visit));
     while ( !que.empty() ) {
         u = que.front();
         que.pop();
         if ( visit[u.x][u.y][u.dist][u.dir] ) 
            continue;
         visit[u.x][u.y][u.dist][u.dir] = 1;
         if ( u.dist == dist && u.dir == edir ) {
            candi.push_back ( Point(u.x,u.y,0,edir) );
            continue;
         }
         for (int i=0;i<4;++i) {
             if ( i == (u.dir+2)%4 || !f[u.x][u.y][i] ) continue;
             int nx = u.x+dx[i], ny = u.y+dy[i];
             if (nx<0 || ny<0 || nx>=N || ny>=N ) continue;
             if ( u.dist == dist ) {  
                if ( i == edir )
                   candi.push_back ( Point(nx,ny,1,edir) );
                continue;  
             }
             que.push ( Point(nx,ny,u.dist+1,i) );
         }
     }
}
void solve (int sx,int sy,int n,int t) {
     candi.clear();
     candi.push_back ( Point(sx,sy,0,0) );
     candi.push_back ( Point(sx,sy,0,2) );
     for (int i=0;i<t;++i)
         simulate (d[i],p[i]);
     ans.clear();
     for (int i=0;i<candi.size();++i)
         if (candi[i].dist) 
            ans.push_back ( make_pair(candi[i].x-dx[candi[i].dir],candi[i].y-dy[candi[i].dir]) );    
         else 
            ans.push_back ( make_pair(candi[i].x,candi[i].y) );
     sort (ans.begin(),ans.end());
     ans.erase ( unique( ans.begin(),ans.end() ),ans.end() );
     for (int i=0;i<ans.size();++i)
         cout<<ans[i].first<<" "<<ans[i].second<<endl;    
}
int main(void) {
    cin.tie(0);
    cin.sync_with_stdio(0);
    int x1, x2, y1, y2, n, t, sx, sy;
    char c;
    while ( cin>>n>>sx>>sy>>t ) {
          memset (f,0,sizeof(f));
          for (int i=0;i<n;++i) {
              cin>>x1>>y1>>x2>>y2;
              if (x1 == x2) {
                 for (int i=min(y1,y2);i<max(y1,y2);++i)
                     f[x1][i][0] = f[x1][i+1][2] = 1;
              }
              if (y1 == y2) {
                 for (int i=min(x1,x2);i<max(x1,x2);++i)
                     f[i][y1][1] = f[i+1][y1][3] = 1;       
              }
          }
          const string dir = "NESW";
          for (int i=0;i<t;++i) {
              cin>>d[i]>>c;
              p[i] = dir.find(c);
          }
          solve (sx,sy,n,t);          
    }
    return 0;    
}
```