#include<bits/stdc++.h>
#define N 1005
using namespace std;
typedef pair<int,int> P;
int n,w,d,x,y,ans;
vector<P> v;
char f;

void add_point(){
  int s,t;
  if(f=='N'){
    s=(x+y<d?x+y+w*2+d:x+y-d);
    t=(w+y-x<d?d-(w+y-x)+w:d-(y-x));
  }
  if(f=='E'){
    s=(d-(y-x)<w?d-(y-x):d-(w+(y-x))+w);
    t=(y+x<w?w-(y+x)+w+d:d-(-w+y+x)+w);
  }
  if(f=='S'){
    s=(0<=-w+y+x?d-(-w+y+x)+w:w-(y+x)+w+d);
    t=(0<=y-x?y-x+w*2+d:w-(-(y-x))+w+d);
  }
  if(f=='W'){
    s=(0<=-(y-x)?w-(-(y-x))+w+d:y-x+w*2+d);
    t=(0<=y+x-d?y+x-d:y+x+w*2+d);
  }
  v.push_back(P(t,s));
}

void solve(){
  int len=v.size();
  for(int i=0;i<len;i++){
    int cnt=1,clock=v[i].first;
    for(int j=i;j<len+i;j++){
      int idx=j%len,c=clock;
      int l=v[idx].second,r=v[idx].first;
      if(l>r)r+=w*2+d*2;
      if(l>c)c+=w*2+d*2;
      if(!(l<=c&&c<=r)){
	clock=v[j].first;
	cnt++;
      }
    }
    ans=min(ans,cnt);
  }
}

int main(){
  cin>>n>>w>>d;
  for(int i=0;i<n;i++){
    cin>>x>>y>>f;
    add_point();
  }
  sort(v.begin(),v.end());
  ans=(1e9);
  solve();
  cout<<ans<<endl;
  return 0;
}
### Prompt

Please formulate a Cpp solution to the following problem:

Example

Input

2 10 6
4 4 E
6 4 W


Output

2

### Response

```cpp
#include<bits/stdc++.h>
#define N 1005
using namespace std;
typedef pair<int,int> P;
int n,w,d,x,y,ans;
vector<P> v;
char f;

void add_point(){
  int s,t;
  if(f=='N'){
    s=(x+y<d?x+y+w*2+d:x+y-d);
    t=(w+y-x<d?d-(w+y-x)+w:d-(y-x));
  }
  if(f=='E'){
    s=(d-(y-x)<w?d-(y-x):d-(w+(y-x))+w);
    t=(y+x<w?w-(y+x)+w+d:d-(-w+y+x)+w);
  }
  if(f=='S'){
    s=(0<=-w+y+x?d-(-w+y+x)+w:w-(y+x)+w+d);
    t=(0<=y-x?y-x+w*2+d:w-(-(y-x))+w+d);
  }
  if(f=='W'){
    s=(0<=-(y-x)?w-(-(y-x))+w+d:y-x+w*2+d);
    t=(0<=y+x-d?y+x-d:y+x+w*2+d);
  }
  v.push_back(P(t,s));
}

void solve(){
  int len=v.size();
  for(int i=0;i<len;i++){
    int cnt=1,clock=v[i].first;
    for(int j=i;j<len+i;j++){
      int idx=j%len,c=clock;
      int l=v[idx].second,r=v[idx].first;
      if(l>r)r+=w*2+d*2;
      if(l>c)c+=w*2+d*2;
      if(!(l<=c&&c<=r)){
	clock=v[j].first;
	cnt++;
      }
    }
    ans=min(ans,cnt);
  }
}

int main(){
  cin>>n>>w>>d;
  for(int i=0;i<n;i++){
    cin>>x>>y>>f;
    add_point();
  }
  sort(v.begin(),v.end());
  ans=(1e9);
  solve();
  cout<<ans<<endl;
  return 0;
}
```