#include<bits/stdc++.h>
using namespace std;

int n,w,d;
struct state {
  int id,x;
  bool in;
  state(){}
  state(int x,int id,bool in):id(id),x(x),in(in){}
  bool operator<(const state& st) const {
    if( x== st.x ) return in > st.in;
    return x < st.x;
  }
};
vector<state> v;
const int INF = 1<<30;
string dc="NESW";

int getX(int id, int x, int y ){
  id%=4;
  if( id == 0 )
    return max( 0, x-(d-y) );
  else if( id == 1 )
    return min( w, x+(d-y) );
  else if( id == 2 )
    return min( w, x+y );  
  return max( 0, x-y );
}
int getY(int id, int x, int y ){
  id%=4;
  if( id == 0 )
    return min( d, y+x );
  else if( id == 1 )
    return min( d, y+(w-x) );
  else if( id == 2 )
    return max( 0, y-(w-x) );
  return max( 0, y-x );
}

int getInter(int x,int y){ 
  if( x == 0 ) return y;
  if( x == w ) return d+w+(d-y);
  if( y == d ) return d+x;
  return 2*d + 2*w - x;
}

int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};

int solve(int st){
  int used[1111]={};
  int m = v.size();
  for(int i=0;i<m;i++)
    if( v[i].in && v[i].id == st ){
      st = i; break;
    }
  queue<int> q;
  int ret = 0;
  //cout << "solve " << endl;
  for(int i=st;i<m;i++){
    state p = v[i];
    //cout << p.id << " " << p.x << " " << p.in << endl;
    if( p.in ) {
      if( !used[p.id] ) {
        used[p.id]++; q.push( p.id );
      }
    } else if( used[p.id] == 1 ) {
      if( q.empty() ) continue;
      ret++;
      while( !q.empty() ) {
        int nid = q.front(); q.pop();
        if( used[nid]==1 ) {
          used[nid]++;
        }
      }
    }
  }
  return ret;
}

int main(){
  cin >> n >> w >> d;
  for(int l=0;l<n;l++){
    int x,y; char c; cin >> x >> y >> c;
    int id;
    for(int i=0;i<4;i++)
      if( dc[i] == c ) id = i;
    int in = getInter( getX( id, x, y ), getY( id, x, y ) );
    int out= getInter( getX( id+1, x, y ), getY( id+1, x, y ) );
    //cout << in << " - " << out << endl;
    v.push_back( state( in, l, true ) );
    v.push_back( state( out, l, false ) );
    v.push_back( state( in+2*d+2*w, l, true ) );
    v.push_back( state( out+2*d+2*w, l, false ) );
    v.push_back( state( in+(2*d+2*w)*2, l, true ) );
    v.push_back( state( out+(2*d+2*w)*2, l, false ) );
  }

  sort( v.begin(), v.end() );
  int res = INF;
  for(int i=0;i<n;i++){
    res = min( res, solve(i) );
  }
  cout << res << endl;
}
### Prompt

Create a solution in CPP for 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;

int n,w,d;
struct state {
  int id,x;
  bool in;
  state(){}
  state(int x,int id,bool in):id(id),x(x),in(in){}
  bool operator<(const state& st) const {
    if( x== st.x ) return in > st.in;
    return x < st.x;
  }
};
vector<state> v;
const int INF = 1<<30;
string dc="NESW";

int getX(int id, int x, int y ){
  id%=4;
  if( id == 0 )
    return max( 0, x-(d-y) );
  else if( id == 1 )
    return min( w, x+(d-y) );
  else if( id == 2 )
    return min( w, x+y );  
  return max( 0, x-y );
}
int getY(int id, int x, int y ){
  id%=4;
  if( id == 0 )
    return min( d, y+x );
  else if( id == 1 )
    return min( d, y+(w-x) );
  else if( id == 2 )
    return max( 0, y-(w-x) );
  return max( 0, y-x );
}

int getInter(int x,int y){ 
  if( x == 0 ) return y;
  if( x == w ) return d+w+(d-y);
  if( y == d ) return d+x;
  return 2*d + 2*w - x;
}

int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};

int solve(int st){
  int used[1111]={};
  int m = v.size();
  for(int i=0;i<m;i++)
    if( v[i].in && v[i].id == st ){
      st = i; break;
    }
  queue<int> q;
  int ret = 0;
  //cout << "solve " << endl;
  for(int i=st;i<m;i++){
    state p = v[i];
    //cout << p.id << " " << p.x << " " << p.in << endl;
    if( p.in ) {
      if( !used[p.id] ) {
        used[p.id]++; q.push( p.id );
      }
    } else if( used[p.id] == 1 ) {
      if( q.empty() ) continue;
      ret++;
      while( !q.empty() ) {
        int nid = q.front(); q.pop();
        if( used[nid]==1 ) {
          used[nid]++;
        }
      }
    }
  }
  return ret;
}

int main(){
  cin >> n >> w >> d;
  for(int l=0;l<n;l++){
    int x,y; char c; cin >> x >> y >> c;
    int id;
    for(int i=0;i<4;i++)
      if( dc[i] == c ) id = i;
    int in = getInter( getX( id, x, y ), getY( id, x, y ) );
    int out= getInter( getX( id+1, x, y ), getY( id+1, x, y ) );
    //cout << in << " - " << out << endl;
    v.push_back( state( in, l, true ) );
    v.push_back( state( out, l, false ) );
    v.push_back( state( in+2*d+2*w, l, true ) );
    v.push_back( state( out+2*d+2*w, l, false ) );
    v.push_back( state( in+(2*d+2*w)*2, l, true ) );
    v.push_back( state( out+(2*d+2*w)*2, l, false ) );
  }

  sort( v.begin(), v.end() );
  int res = INF;
  for(int i=0;i<n;i++){
    res = min( res, solve(i) );
  }
  cout << res << endl;
}
```