#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int to_i(char c)
{
	return c=='E'?0:c=='S'?1:c=='W'?2:3;
}
int N,T;
bool G[55][55][4];
int dx[4]={1,0,-1,0},dy[4]={0,-1,0,1};
int main()
{
	int nx,ny;
	cin>>N>>nx>>ny>>T;
	for(int i=0;i<N;i++)
	{
		int xs,ys,xe,ye;
		cin>>xs>>ys>>xe>>ye;
		if(xs==xe)
		{
			if(ys<ye)
			{
				for(int y=ys;y<ye;y++)
				{
					G[xs][y][3]=true;
					G[xs][y+1][1]=true;
				}
			}
			else
			{
				for(int y=ye;y<ys;y++)
				{
					G[xs][y][3]=true;
					G[xs][y+1][1]=true;
				}
			}
		}
		else
		{
			if(xs<xe)
			{
				for(int x=xs;x<xe;x++)
				{
					G[x][ys][0]=true;
					G[x+1][ys][2]=true;
				}
			}
			else
			{
				for(int x=xe;x<xs;x++)
				{
					G[x][ys][0]=true;
					G[x+1][ys][2]=true;
				}
			}
		}
	}
	vector<pair<pair<int,int>,pair<int,bool> > >now;
	for(int r=0;r<4;r++)
	{
		now.push_back(make_pair(make_pair(nx,ny),make_pair(r,false)));
	}
	for(;T--;)
	{
		int d;char c;cin>>d>>c;
		for(int k=0;k<d;k++)
		{
			vector<pair<pair<int,int>,pair<int,bool> > >nxt;
			for(pair<pair<int,int>,pair<int,bool> >p:now)
			{
				int x=p.first.first,y=p.first.second;
				if(p.second.second)
				{
					int od=(p.second.first+2)%4;
					for(int nr=0;nr<4;nr++)
					{
						if(nr==od)continue;
						if(G[x][y][nr])
						{
							nxt.push_back(make_pair(make_pair(x+dx[nr],y+dy[nr]),make_pair(nr,true)));
						}
					}
				}
				else
				{
					int nr=p.second.first;
					if(G[x][y][nr])
					{
						nxt.push_back(make_pair(make_pair(x+dx[nr],y+dy[nr]),make_pair(nr,true)));
					}
				}
			}
			sort(nxt.begin(),nxt.end());
			now=vector<pair<pair<int,int>,pair<int,bool> > >(nxt.begin(),unique(nxt.begin(),nxt.end()));
		}
		vector<pair<pair<int,int>,pair<int,bool> > >tmp=now;
		now.clear();
		int cd=to_i(c);
		int od=(to_i(c)+2)%4;
		for(pair<pair<int,int>,pair<int,bool> >p:tmp)
		{
			if(p.second.first==cd)
			{
				now.push_back(make_pair(p.first,make_pair(cd,true)));
			}
			else if(p.second.first!=od&&G[p.first.first][p.first.second][cd])
			{
				now.push_back(make_pair(p.first,make_pair(cd,false)));
			}
		}
	}
	vector<pair<int,int> >ans;
	for(pair<pair<int,int>,pair<int,bool> >p:now)ans.push_back(p.first);
	sort(ans.begin(),ans.end());
	ans.erase(unique(ans.begin(),ans.end()),ans.end());
	for(pair<int,int>p:ans)cout<<p.first<<" "<<p.second<<endl;
}


### Prompt

Please create a solution in Cpp 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<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int to_i(char c)
{
	return c=='E'?0:c=='S'?1:c=='W'?2:3;
}
int N,T;
bool G[55][55][4];
int dx[4]={1,0,-1,0},dy[4]={0,-1,0,1};
int main()
{
	int nx,ny;
	cin>>N>>nx>>ny>>T;
	for(int i=0;i<N;i++)
	{
		int xs,ys,xe,ye;
		cin>>xs>>ys>>xe>>ye;
		if(xs==xe)
		{
			if(ys<ye)
			{
				for(int y=ys;y<ye;y++)
				{
					G[xs][y][3]=true;
					G[xs][y+1][1]=true;
				}
			}
			else
			{
				for(int y=ye;y<ys;y++)
				{
					G[xs][y][3]=true;
					G[xs][y+1][1]=true;
				}
			}
		}
		else
		{
			if(xs<xe)
			{
				for(int x=xs;x<xe;x++)
				{
					G[x][ys][0]=true;
					G[x+1][ys][2]=true;
				}
			}
			else
			{
				for(int x=xe;x<xs;x++)
				{
					G[x][ys][0]=true;
					G[x+1][ys][2]=true;
				}
			}
		}
	}
	vector<pair<pair<int,int>,pair<int,bool> > >now;
	for(int r=0;r<4;r++)
	{
		now.push_back(make_pair(make_pair(nx,ny),make_pair(r,false)));
	}
	for(;T--;)
	{
		int d;char c;cin>>d>>c;
		for(int k=0;k<d;k++)
		{
			vector<pair<pair<int,int>,pair<int,bool> > >nxt;
			for(pair<pair<int,int>,pair<int,bool> >p:now)
			{
				int x=p.first.first,y=p.first.second;
				if(p.second.second)
				{
					int od=(p.second.first+2)%4;
					for(int nr=0;nr<4;nr++)
					{
						if(nr==od)continue;
						if(G[x][y][nr])
						{
							nxt.push_back(make_pair(make_pair(x+dx[nr],y+dy[nr]),make_pair(nr,true)));
						}
					}
				}
				else
				{
					int nr=p.second.first;
					if(G[x][y][nr])
					{
						nxt.push_back(make_pair(make_pair(x+dx[nr],y+dy[nr]),make_pair(nr,true)));
					}
				}
			}
			sort(nxt.begin(),nxt.end());
			now=vector<pair<pair<int,int>,pair<int,bool> > >(nxt.begin(),unique(nxt.begin(),nxt.end()));
		}
		vector<pair<pair<int,int>,pair<int,bool> > >tmp=now;
		now.clear();
		int cd=to_i(c);
		int od=(to_i(c)+2)%4;
		for(pair<pair<int,int>,pair<int,bool> >p:tmp)
		{
			if(p.second.first==cd)
			{
				now.push_back(make_pair(p.first,make_pair(cd,true)));
			}
			else if(p.second.first!=od&&G[p.first.first][p.first.second][cd])
			{
				now.push_back(make_pair(p.first,make_pair(cd,false)));
			}
		}
	}
	vector<pair<int,int> >ans;
	for(pair<pair<int,int>,pair<int,bool> >p:now)ans.push_back(p.first);
	sort(ans.begin(),ans.end());
	ans.erase(unique(ans.begin(),ans.end()),ans.end());
	for(pair<int,int>p:ans)cout<<p.first<<" "<<p.second<<endl;
}


```