#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
int N,W,H,L;
vector<P> t;

bool check(P p,int a){
  if(p.first<p.second)
    return (p.first<=a&&a<=p.second);
  return (p.first<=a||a<=p.second);
}
int solve(int si){
  int res=1,last=t[si].second;
  for(int i=si;i<si+N;i++){
    if(check(t[i],last)) continue;
    res++;
    last=t[i].second;
  }
  return res;
}
int main(){
  cin>>N>>W>>H;
  L=W+W+H+H;
  for(int i=0;i<N;i++){
    int x,y,a,b;
    char ch;
    cin>>x>>y>>ch;
    if(ch=='N'){
      a = (x+y+L)%L;
      b = (H+x-y+H)%L;
    }
    if(ch=='E'){
      a = (H+H-y+x+L)%L;
      b = (L-y-x)%L;
    }
    if(ch=='S'){
      a = (L-x-y+L)%L;
      b = (L-x+y)%L;
    }
    if(ch=='W'){
      a = (y-x+L)%L;
      b = (y+x)%L;
    } 
    t.push_back(P(a,b));
  }
  for(int i=0;i<N;i++) swap(t[i].first,t[i].second);
  sort(t.begin(),t.end());
  for(int i=0;i<N;i++) t.push_back(t[i]);
  for(int i=0;i<N+N;i++) swap(t[i].first,t[i].second);
  int ans = N;
  for(int i=0;i<N;i++)ans = min(ans,solve(i));
  cout<<ans<<endl;
  return 0;
}
### Prompt

Your challenge is to write 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>
using namespace std;
typedef pair<int,int> P;
int N,W,H,L;
vector<P> t;

bool check(P p,int a){
  if(p.first<p.second)
    return (p.first<=a&&a<=p.second);
  return (p.first<=a||a<=p.second);
}
int solve(int si){
  int res=1,last=t[si].second;
  for(int i=si;i<si+N;i++){
    if(check(t[i],last)) continue;
    res++;
    last=t[i].second;
  }
  return res;
}
int main(){
  cin>>N>>W>>H;
  L=W+W+H+H;
  for(int i=0;i<N;i++){
    int x,y,a,b;
    char ch;
    cin>>x>>y>>ch;
    if(ch=='N'){
      a = (x+y+L)%L;
      b = (H+x-y+H)%L;
    }
    if(ch=='E'){
      a = (H+H-y+x+L)%L;
      b = (L-y-x)%L;
    }
    if(ch=='S'){
      a = (L-x-y+L)%L;
      b = (L-x+y)%L;
    }
    if(ch=='W'){
      a = (y-x+L)%L;
      b = (y+x)%L;
    } 
    t.push_back(P(a,b));
  }
  for(int i=0;i<N;i++) swap(t[i].first,t[i].second);
  sort(t.begin(),t.end());
  for(int i=0;i<N;i++) t.push_back(t[i]);
  for(int i=0;i<N+N;i++) swap(t[i].first,t[i].second);
  int ans = N;
  for(int i=0;i<N;i++)ans = min(ans,solve(i));
  cout<<ans<<endl;
  return 0;
}
```