#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using std::cerr;
using std::cin;
using std::cout;
using std::endl;

typedef std::pair<int,int> ii;

bool IsContain(ii pos,int h,int w){
  if(1<=pos.first&&pos.first<=w-1&&1<=pos.second&pos.second<=h-1){
    return true;
  }else{
    return false;
  }
}

int GetPos(ii pos,int h,int w){
  int result=0;
  if(pos.first==0){
    result= 2*w+h+(h-pos.second);
  }else if(pos.first==w){
    result= w+pos.second;
  }else if(pos.second==0){
    result= pos.first;
  }else{
   result= w+h+(w-pos.first);
  }
  // if(result>=(h+w)*2){
  //   result=0;
  // }
  return result;
}



int Solve(std::vector<ii> job,int start,int d,int w,int it){
  int result=1;
  int time=start;
  int start_itr=it;

  int itr=start_itr;
  bool looped=false;
  while(true){
    if(itr==start_itr&&looped){
      break;
    }
    if(job[itr].first<job[itr].second){
      if(!(job[itr].first<=time&&time<=job[itr].second)){
        time=job[itr].second;
        result++;
      }
    }else{
      if(!((job[itr].first<=time&&time<=2*(d+w))||(0<=time&&time<=job[itr].second))){
        time=job[itr].second;
        result++;
      }
    }
    itr++;
    if(itr>=job.size()){
      looped=true;
      itr=0;
    }
  }

  return result;
}

int main(void) {
  cout << std::fixed << std::setprecision(10);
  cin.tie(0);
  std::ios::sync_with_stdio(false);

  int n,w,d;
  cin>>n>>w>>d;
  std::vector<ii> job;
  for(int i=0;i<n;i++){
    int x,y;
    char f;
    cin>>x>>y>>f;
    int limit_l,limit_r;
    ii l_pos=std::make_pair(x,y);
    ii r_pos=l_pos;
    if(f=='E'){
      while(IsContain(l_pos,d,w)){
        l_pos.first++;
        l_pos.second--;
      }
      while(IsContain(r_pos,d,w)){
        r_pos.first++;
        r_pos.second++;
      }
    } else if(f=='W'){
      while(IsContain(l_pos,d,w)){
        l_pos.first--;
        l_pos.second++;
      }
      while(IsContain(r_pos,d,w)){
        r_pos.first--;
        r_pos.second--;
      }
    } else if(f=='N'){
      while(IsContain(l_pos,d,w)){
        l_pos.first++;
        l_pos.second++;
      }
      while(IsContain(r_pos,d,w)){
        r_pos.first--;
        r_pos.second++;
      }
    } else {//f=='S'
      while(IsContain(l_pos,d,w)){
        l_pos.first--;
        l_pos.second--;
      }
      while(IsContain(r_pos,d,w)){
        r_pos.first++;
        r_pos.second--;
      }
    }

    limit_l=GetPos(l_pos,d,w);
    limit_r=GetPos(r_pos,d,w);
    if(limit_r==0){
      limit_r=32;
    }

    job.push_back(std::make_pair(limit_l,limit_r));
  }

  int result=INT32_MAX;
  std::sort(job.begin(), job.end(),[](ii a,ii b){
    return a.second<b.second;
  });

  for(int i=0;i<2*n;i++){
    if(i%2==0){
      result=std::min(result,Solve(job,job[i/2].first,d,w,i/2));
    }else{
      result=std::min(result,Solve(job,job[i/2].second,d,w,i/2));
    }


  }
  cout<<result<<endl;


  return 0;
}

### Prompt

Develop a solution in Cpp to the problem described below:

Example

Input

2 10 6
4 4 E
6 4 W


Output

2

### Response

```cpp
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using std::cerr;
using std::cin;
using std::cout;
using std::endl;

typedef std::pair<int,int> ii;

bool IsContain(ii pos,int h,int w){
  if(1<=pos.first&&pos.first<=w-1&&1<=pos.second&pos.second<=h-1){
    return true;
  }else{
    return false;
  }
}

int GetPos(ii pos,int h,int w){
  int result=0;
  if(pos.first==0){
    result= 2*w+h+(h-pos.second);
  }else if(pos.first==w){
    result= w+pos.second;
  }else if(pos.second==0){
    result= pos.first;
  }else{
   result= w+h+(w-pos.first);
  }
  // if(result>=(h+w)*2){
  //   result=0;
  // }
  return result;
}



int Solve(std::vector<ii> job,int start,int d,int w,int it){
  int result=1;
  int time=start;
  int start_itr=it;

  int itr=start_itr;
  bool looped=false;
  while(true){
    if(itr==start_itr&&looped){
      break;
    }
    if(job[itr].first<job[itr].second){
      if(!(job[itr].first<=time&&time<=job[itr].second)){
        time=job[itr].second;
        result++;
      }
    }else{
      if(!((job[itr].first<=time&&time<=2*(d+w))||(0<=time&&time<=job[itr].second))){
        time=job[itr].second;
        result++;
      }
    }
    itr++;
    if(itr>=job.size()){
      looped=true;
      itr=0;
    }
  }

  return result;
}

int main(void) {
  cout << std::fixed << std::setprecision(10);
  cin.tie(0);
  std::ios::sync_with_stdio(false);

  int n,w,d;
  cin>>n>>w>>d;
  std::vector<ii> job;
  for(int i=0;i<n;i++){
    int x,y;
    char f;
    cin>>x>>y>>f;
    int limit_l,limit_r;
    ii l_pos=std::make_pair(x,y);
    ii r_pos=l_pos;
    if(f=='E'){
      while(IsContain(l_pos,d,w)){
        l_pos.first++;
        l_pos.second--;
      }
      while(IsContain(r_pos,d,w)){
        r_pos.first++;
        r_pos.second++;
      }
    } else if(f=='W'){
      while(IsContain(l_pos,d,w)){
        l_pos.first--;
        l_pos.second++;
      }
      while(IsContain(r_pos,d,w)){
        r_pos.first--;
        r_pos.second--;
      }
    } else if(f=='N'){
      while(IsContain(l_pos,d,w)){
        l_pos.first++;
        l_pos.second++;
      }
      while(IsContain(r_pos,d,w)){
        r_pos.first--;
        r_pos.second++;
      }
    } else {//f=='S'
      while(IsContain(l_pos,d,w)){
        l_pos.first--;
        l_pos.second--;
      }
      while(IsContain(r_pos,d,w)){
        r_pos.first++;
        r_pos.second--;
      }
    }

    limit_l=GetPos(l_pos,d,w);
    limit_r=GetPos(r_pos,d,w);
    if(limit_r==0){
      limit_r=32;
    }

    job.push_back(std::make_pair(limit_l,limit_r));
  }

  int result=INT32_MAX;
  std::sort(job.begin(), job.end(),[](ii a,ii b){
    return a.second<b.second;
  });

  for(int i=0;i<2*n;i++){
    if(i%2==0){
      result=std::min(result,Solve(job,job[i/2].first,d,w,i/2));
    }else{
      result=std::min(result,Solve(job,job[i/2].second,d,w,i/2));
    }


  }
  cout<<result<<endl;


  return 0;
}

```