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

#define mem(t, v)   memset ((t) , v, sizeof(t))
#define all(x)      x.begin(),x.end()
#define un(x)       x.erase(unique(all(x)), x.end())
#define sf(n)       scanf("%d", &n)
#define sff(a,b)    scanf("%d %d", &a, &b)
#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
#define sl(n)       scanf("%lld", &n)
#define sll(a,b)    scanf("%lld %lld", &a, &b)
#define slll(a,b,c) scanf("%lld %lld %lld", &a, &b, &c)
#define D(x)        cerr << __LINE__ << ": " << #x << " = " << (x) << '\n'
#define DD(x,y)     cerr << __LINE__ << ": " << #x << " = " << x << "   " << #y << " = " << y << '\n'
#define DDD(x,y,z)  cerr << __LINE__ << ": " << #x << " = " << x << "   " << #y << " = " << y << "   " << #z << " = " << z << '\n'
#define DBG         cerr << __LINE__ << ": Hi" << '\n'
#define pb          push_back
#define PI          acos(-1.00)
#define xx          first
#define yy          second

typedef unsigned long long int ULL;
typedef long long int LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;


inline int setBit(int N, int pos) { return N=N | (1<<pos); }
inline int resetBit(int N, int pos) { return N= N & ~(1<<pos); }
inline bool checkBit(int N, int pos) { return (bool)(N & (1<<pos)); }

#define SOUTH       0
#define NORTH       1
#define EAST        2
#define WEST        3

///          S   N   E   W
int fx[] = {+0, +0, +1, -1};// -1, +1, -1, +1};
int fy[] = {-1, +1, +0, +0};// +1, +1, -1, -1}; //Four & Eight Direction
int opo[] ={ 1,  0,  3,  2};
int n;
pii src;
int total;
bool vis[60][60][110][12][5], can[60][60][5];
pii state[110];
void dfs(int r, int c, int t, int moved, int dir)
{
    if(t > total)
        return;
//    DDD(r, c, moved);
    if(vis[r][c][t][moved][dir])
        return;
    vis[r][c][t][moved][dir] = true;
    if(moved == state[t].xx)
    {
        if(dir == state[t].yy)
        {
            for(int i = 0; i<4; i++)
            {
                if(opo[dir] == i)
                    continue;
                if(can[r][c][i])
                    dfs(r+fx[i], c+fy[i], t+1, 1, i);
            }
        }
        else
        {
            if(can[r][c][state[t].yy] && opo[dir] != state[t].yy)
                dfs(r+fx[state[t].yy], c+fy[state[t].yy], t+1, 1, state[t].yy);
        }
        return;
    }


    /// moved != state[t].xx
    for(int i = 0; i<4; i++)
    {
        if(opo[dir] == i)
            continue;
        if(can[r][c][i])
            dfs(r+fx[i], c+fy[i], t, moved+1, i);
    }
}

int getDir(pii u, pii v)
{
    if(u.xx == v.xx)
    {
        if(u.yy < v.yy)
            return NORTH;
        else
            return SOUTH;
    }
    else
    {
        if(u.xx < v.xx)
            return EAST;
        else
            return WEST;
    }
}

void go(pii u, pii v, int dir)
{
    if(u == v)
        return;
    can[u.xx][u.yy][dir] = true;
    u.xx += fx[dir];
    u.yy += fy[dir];
    go(u, v, dir);
}

vector<pii>sltn;


int main()
{
//    freopen("maxon.txt", "r", stdin);
//    D(sizeof(vis)/1024/1024);
    sf(n);
    sff(src.xx, src.yy);
    sf(total);
    for(int i = 1; i<=n; i++)
    {
        pii u, v;
        sff(u.xx, u.yy);
        sff(v.xx, v.yy);
        int dir = getDir(u, v);
        go(u, v, dir);
        dir = getDir(v, u);
        go(v, u, dir);
    }
    for(int i = 1; i<=total; i++)
    {
        sf(state[i].xx);
        char s[5];
        scanf("%s",s);
        if(s[0] == 'N')
            state[i].yy = NORTH;
        else if(s[0] == 'S')
            state[i].yy = SOUTH;
        else if(s[0] == 'E')
            state[i].yy = EAST;
        else if(s[0] == 'W')
            state[i].yy = WEST;
    }
    for(int dir = 0; dir<4; dir++)
    {
        if(can[src.xx][src.yy][dir])
            dfs(src.xx+fx[dir], src.yy+fy[dir], 1, 1, dir);
    }
    for(int r = 0; r<=50; r++)
    {
        for(int c = 0; c<=50; c++)
        {
            bool ok = false;
            for(int dir = 0; dir<4; dir++)
            {
                if(vis[r][c][total][state[total].xx][dir] == 0)
                    continue;
                if(dir == state[total].yy)
                    ok = true;
                else
                {
                    if(can[r][c][state[total].yy] && opo[dir] != state[total].yy)
                        ok = true;
                }
            }
            if(ok)
                sltn.pb({r, c});
        }
    }
    assert(sltn.size() >= 1);
    for(auto v: sltn)
        printf("%d %d\n",v.xx, v.yy);

    return 0;
}



### Prompt

Develop a solution in cpp 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>
using namespace std;

#define mem(t, v)   memset ((t) , v, sizeof(t))
#define all(x)      x.begin(),x.end()
#define un(x)       x.erase(unique(all(x)), x.end())
#define sf(n)       scanf("%d", &n)
#define sff(a,b)    scanf("%d %d", &a, &b)
#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
#define sl(n)       scanf("%lld", &n)
#define sll(a,b)    scanf("%lld %lld", &a, &b)
#define slll(a,b,c) scanf("%lld %lld %lld", &a, &b, &c)
#define D(x)        cerr << __LINE__ << ": " << #x << " = " << (x) << '\n'
#define DD(x,y)     cerr << __LINE__ << ": " << #x << " = " << x << "   " << #y << " = " << y << '\n'
#define DDD(x,y,z)  cerr << __LINE__ << ": " << #x << " = " << x << "   " << #y << " = " << y << "   " << #z << " = " << z << '\n'
#define DBG         cerr << __LINE__ << ": Hi" << '\n'
#define pb          push_back
#define PI          acos(-1.00)
#define xx          first
#define yy          second

typedef unsigned long long int ULL;
typedef long long int LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;


inline int setBit(int N, int pos) { return N=N | (1<<pos); }
inline int resetBit(int N, int pos) { return N= N & ~(1<<pos); }
inline bool checkBit(int N, int pos) { return (bool)(N & (1<<pos)); }

#define SOUTH       0
#define NORTH       1
#define EAST        2
#define WEST        3

///          S   N   E   W
int fx[] = {+0, +0, +1, -1};// -1, +1, -1, +1};
int fy[] = {-1, +1, +0, +0};// +1, +1, -1, -1}; //Four & Eight Direction
int opo[] ={ 1,  0,  3,  2};
int n;
pii src;
int total;
bool vis[60][60][110][12][5], can[60][60][5];
pii state[110];
void dfs(int r, int c, int t, int moved, int dir)
{
    if(t > total)
        return;
//    DDD(r, c, moved);
    if(vis[r][c][t][moved][dir])
        return;
    vis[r][c][t][moved][dir] = true;
    if(moved == state[t].xx)
    {
        if(dir == state[t].yy)
        {
            for(int i = 0; i<4; i++)
            {
                if(opo[dir] == i)
                    continue;
                if(can[r][c][i])
                    dfs(r+fx[i], c+fy[i], t+1, 1, i);
            }
        }
        else
        {
            if(can[r][c][state[t].yy] && opo[dir] != state[t].yy)
                dfs(r+fx[state[t].yy], c+fy[state[t].yy], t+1, 1, state[t].yy);
        }
        return;
    }


    /// moved != state[t].xx
    for(int i = 0; i<4; i++)
    {
        if(opo[dir] == i)
            continue;
        if(can[r][c][i])
            dfs(r+fx[i], c+fy[i], t, moved+1, i);
    }
}

int getDir(pii u, pii v)
{
    if(u.xx == v.xx)
    {
        if(u.yy < v.yy)
            return NORTH;
        else
            return SOUTH;
    }
    else
    {
        if(u.xx < v.xx)
            return EAST;
        else
            return WEST;
    }
}

void go(pii u, pii v, int dir)
{
    if(u == v)
        return;
    can[u.xx][u.yy][dir] = true;
    u.xx += fx[dir];
    u.yy += fy[dir];
    go(u, v, dir);
}

vector<pii>sltn;


int main()
{
//    freopen("maxon.txt", "r", stdin);
//    D(sizeof(vis)/1024/1024);
    sf(n);
    sff(src.xx, src.yy);
    sf(total);
    for(int i = 1; i<=n; i++)
    {
        pii u, v;
        sff(u.xx, u.yy);
        sff(v.xx, v.yy);
        int dir = getDir(u, v);
        go(u, v, dir);
        dir = getDir(v, u);
        go(v, u, dir);
    }
    for(int i = 1; i<=total; i++)
    {
        sf(state[i].xx);
        char s[5];
        scanf("%s",s);
        if(s[0] == 'N')
            state[i].yy = NORTH;
        else if(s[0] == 'S')
            state[i].yy = SOUTH;
        else if(s[0] == 'E')
            state[i].yy = EAST;
        else if(s[0] == 'W')
            state[i].yy = WEST;
    }
    for(int dir = 0; dir<4; dir++)
    {
        if(can[src.xx][src.yy][dir])
            dfs(src.xx+fx[dir], src.yy+fy[dir], 1, 1, dir);
    }
    for(int r = 0; r<=50; r++)
    {
        for(int c = 0; c<=50; c++)
        {
            bool ok = false;
            for(int dir = 0; dir<4; dir++)
            {
                if(vis[r][c][total][state[total].xx][dir] == 0)
                    continue;
                if(dir == state[total].yy)
                    ok = true;
                else
                {
                    if(can[r][c][state[total].yy] && opo[dir] != state[total].yy)
                        ok = true;
                }
            }
            if(ok)
                sltn.pb({r, c});
        }
    }
    assert(sltn.size() >= 1);
    for(auto v: sltn)
        printf("%d %d\n",v.xx, v.yy);

    return 0;
}



```