#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<ll, P> P3;
typedef pair<P, P> PP;


constexpr int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
constexpr int N = 0, E = 1, S = 2, W = 3;
string dir = "NESW";
bool connected[55][55][4];

set<PP> pos, tmp;

void move(){
    tmp.clear();
    for(auto &pp : pos){
        int x, y, now, pre;
        x = pp.first.first;
        y = pp.first.second;
        now = pp.second.first;
        pre = pp.second.second;
        int nx = x+dx[now], ny = y+dy[now];
        for(int i=0;i<4;i++){
            if(i==(now+2)%4) continue;
            if(!connected[nx][ny][i]) continue;
            tmp.insert({{nx,ny},{i,now}});
        }
    }
    pos = tmp;
}

int main() {
    int n, x0, y0, T;
    cin >> n >> x0 >> y0 >> T;
    for(int i=0;i<n;i++){
        int xs, ys, xe, ye;
        cin >> xs >> ys >> xe >> ye;
        if(xs == xe){
            if(ys > ye) swap(ys, ye);
            for(int y = ys; y < ye; y++){
                connected[xs][y][N] = true;
                connected[xs][y+1][S] = true;
            }
        }
        else{
            if(xs > xe) swap(xs, xe);
            for(int x = xs; x < xe; x++){
                connected[x][ys][E] = true;
                connected[x+1][ys][W] = true;
            }
        }
    }
    for(int i=0;i<4;i++){
        if(connected[x0][y0][i]){
            pos.insert({{x0,y0},{i,-1}});
        }
    }
    for(int i=0;i<T;i++){
        int d;
        char c;
        cin >> d >> c;
        for(int j=0;j<d;j++){
            move();
        }
        tmp.clear();
        for(auto &pp : pos){
            int now = pp.second.first, pre = pp.second.second;
            if(dir[now] == c || dir[pre] == c){
                tmp.insert(pp);
            }
        }
        pos = tmp;
    }
    set<P> ans;
    for(auto pp : pos){
        int x, y;
        x = pp.first.first;
        y = pp.first.second;
        ans.insert({x,y});
    }
    for(auto p : ans){
        cout << p.first << " " << p.second << endl;
    }
    return 0;
}


### Prompt

Generate 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;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<ll, P> P3;
typedef pair<P, P> PP;


constexpr int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
constexpr int N = 0, E = 1, S = 2, W = 3;
string dir = "NESW";
bool connected[55][55][4];

set<PP> pos, tmp;

void move(){
    tmp.clear();
    for(auto &pp : pos){
        int x, y, now, pre;
        x = pp.first.first;
        y = pp.first.second;
        now = pp.second.first;
        pre = pp.second.second;
        int nx = x+dx[now], ny = y+dy[now];
        for(int i=0;i<4;i++){
            if(i==(now+2)%4) continue;
            if(!connected[nx][ny][i]) continue;
            tmp.insert({{nx,ny},{i,now}});
        }
    }
    pos = tmp;
}

int main() {
    int n, x0, y0, T;
    cin >> n >> x0 >> y0 >> T;
    for(int i=0;i<n;i++){
        int xs, ys, xe, ye;
        cin >> xs >> ys >> xe >> ye;
        if(xs == xe){
            if(ys > ye) swap(ys, ye);
            for(int y = ys; y < ye; y++){
                connected[xs][y][N] = true;
                connected[xs][y+1][S] = true;
            }
        }
        else{
            if(xs > xe) swap(xs, xe);
            for(int x = xs; x < xe; x++){
                connected[x][ys][E] = true;
                connected[x+1][ys][W] = true;
            }
        }
    }
    for(int i=0;i<4;i++){
        if(connected[x0][y0][i]){
            pos.insert({{x0,y0},{i,-1}});
        }
    }
    for(int i=0;i<T;i++){
        int d;
        char c;
        cin >> d >> c;
        for(int j=0;j<d;j++){
            move();
        }
        tmp.clear();
        for(auto &pp : pos){
            int now = pp.second.first, pre = pp.second.second;
            if(dir[now] == c || dir[pre] == c){
                tmp.insert(pp);
            }
        }
        pos = tmp;
    }
    set<P> ans;
    for(auto pp : pos){
        int x, y;
        x = pp.first.first;
        y = pp.first.second;
        ans.insert({x,y});
    }
    for(auto p : ans){
        cout << p.first << " " << p.second << endl;
    }
    return 0;
}


```