#include<bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef pair<int,int>P;
int dx[]={1,1,-1,-1};
int dy[]={-1,1,1,-1};
int Con(char c){
  if(c=='S')return 3;
  if(c=='E')return 0;
  if(c=='N')return 1;
  if(c=='W')return 2;
}
int x,y,X,Y,n,w,h,l,r,d,cnt,ans=1e7;
char c;
map<P,int>m;
void init(){
  r(i,w+1)m[P(0,i)]=cnt++;
  r(i,h+1)m[P(i,w)]=cnt++;
  r(i,w+1)m[P(h,w-i)]=cnt++;
  r(i,h+1)m[P(h-i,0)]=cnt++;
}
signed main(){
  vector<P>v;
  cin>>n>>w>>h;
  init();
  r(i,n){
    cin>>X>>Y>>c;
    d=Con(c);
    x=X;y=Y;
    while(0<x&&x<w&&0<y&&y<h){
      x+=dx[d];
      y+=dy[d];
    }
    l=m[P(y,x)];
    x=X;y=Y;
    while(0<x&&x<w&&0<y&&y<h){
      x+=dx[(d+1)%4];
      y+=dy[(d+1)%4];
    }
    r=m[P(y,x)];
    v.push_back(P(r,l));
  }
  sort(v.begin(),v.end());
  r(i,n){
    int now=v[i].first,count=1;
    for(int k=0,j=i;k<n;k++,j=(j+1)%n){
      r=v[j].first;
      l=v[j].second;
      if(l>r){
        if(!((l<=now&&now<=cnt)||(0<=now&&now<=r))){
          now=r;
          count++;
        }
      }
      else{
        if(!(l<=now&&now<=r)){
          now=r;
          count++;
        }
      }
    }
    ans=min(ans,count);
  }
  cout<<ans<<endl;
}

### Prompt

Please provide a CPP coded solution to the problem described below:

Example

Input

2 10 6
4 4 E
6 4 W


Output

2

### Response

```cpp
#include<bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef pair<int,int>P;
int dx[]={1,1,-1,-1};
int dy[]={-1,1,1,-1};
int Con(char c){
  if(c=='S')return 3;
  if(c=='E')return 0;
  if(c=='N')return 1;
  if(c=='W')return 2;
}
int x,y,X,Y,n,w,h,l,r,d,cnt,ans=1e7;
char c;
map<P,int>m;
void init(){
  r(i,w+1)m[P(0,i)]=cnt++;
  r(i,h+1)m[P(i,w)]=cnt++;
  r(i,w+1)m[P(h,w-i)]=cnt++;
  r(i,h+1)m[P(h-i,0)]=cnt++;
}
signed main(){
  vector<P>v;
  cin>>n>>w>>h;
  init();
  r(i,n){
    cin>>X>>Y>>c;
    d=Con(c);
    x=X;y=Y;
    while(0<x&&x<w&&0<y&&y<h){
      x+=dx[d];
      y+=dy[d];
    }
    l=m[P(y,x)];
    x=X;y=Y;
    while(0<x&&x<w&&0<y&&y<h){
      x+=dx[(d+1)%4];
      y+=dy[(d+1)%4];
    }
    r=m[P(y,x)];
    v.push_back(P(r,l));
  }
  sort(v.begin(),v.end());
  r(i,n){
    int now=v[i].first,count=1;
    for(int k=0,j=i;k<n;k++,j=(j+1)%n){
      r=v[j].first;
      l=v[j].second;
      if(l>r){
        if(!((l<=now&&now<=cnt)||(0<=now&&now<=r))){
          now=r;
          count++;
        }
      }
      else{
        if(!(l<=now&&now<=r)){
          now=r;
          count++;
        }
      }
    }
    ans=min(ans,count);
  }
  cout<<ans<<endl;
}

```