#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using P = pair<int, int>;
const double eps = 1e-8;
const ll MOD = 1000000007;
const int INF = INT_MAX / 2;
const ll LINF = LLONG_MAX / 2;
template <typename T1, typename T2>
bool chmax(T1 &a, const T2 &b) {
  if(a < b) {a = b; return true;}
  return false;
}
template <typename T1, typename T2>
bool chmin(T1 &a, const T2 &b) {
  if(a > b) {a = b; return true;}
  return false;
}
template<typename T1, typename T2>
ostream& operator<<(ostream &os, const pair<T1, T2> p) {
  os << p.first << ":" << p.second;
  return os;
}
template<class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  for(int i=0;i<((int)(v.size()));++i) {
    if(i) os << " ";
    os << v[i];
  }
  return os;
}
P pos0(int i, int j, int w, int d) {
  int mi = min(i, j);
  return make_pair(i-mi, j-mi);
}
P pos1(int i, int j, int w, int d) {
  int mi = min(i, w-j);
  return make_pair(i-mi, j+mi);
}
P pos2(int i, int j, int w, int d) {
  int mi = min(d-i, w-j);
  return make_pair(i+mi, j+mi);
}
P pos3(int i, int j, int w, int d) {
  int mi = min(d-i, j);
  return make_pair(i+mi, j-mi);
}
int rect_to_range(int r, int c, int w, int d) {
  if(r == 0 && c != w) {
    return c;
  } else if(c == w && r != d) {
    return w + r;
  } else if(r == d && c != 0) {
    return w + d + (w-c);
  } else {
    return 2 * w + d + (d-r);
  }
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  int n, w, d; cin >> n >> w >> d;
  vector<P> v(3*n);
  for(int i=0;i<(n);++i) {
    int x, y; char f; cin >> x >> y >> f;
    P l, r;
    if(f == 'S') {
      l = pos0(y, x, w, d);
      r = pos1(y, x, w, d);
    } else if(f == 'E') {
      l = pos1(y, x, w, d);
      r = pos2(y, x, w, d);
    } else if(f == 'N') {
      l = pos2(y, x, w, d);
      r = pos3(y, x, w, d);
    } else {
      l = pos3(y, x, w, d);
      r = pos0(y, x, w, d);
    }
    v[i].first = rect_to_range(l.first, l.second, w, d);
    v[i].second = rect_to_range(r.first, r.second, w, d);
    if(v[i].first > v[i].second) v[i].second += 2 * (w + d);
  }
  for(int i=(n);i<(2*n);++i) {
    v[i].first = v[i-n].first + 2*(w+d);
    v[i].second = v[i-n].second + 2*(w+d);
  }
  for(int i=(2*n);i<(3*n);++i) {
    v[i].first = v[i-n].first + 2*(w+d);
    v[i].second = v[i-n].second + 2*(w+d);
  }
  set<int> st;
  for(int i=0;i<(3*n);++i) {
    st.insert(v[i].first);
    st.insert(v[i].second);
  }
  map<int, int> mp;
  int id = 0;
  for(auto &e: st) {
    mp[e] = id;
    id++;
  }
  for(int i=0;i<(3*n);++i) {
    v[i].first = mp[v[i].first];
    v[i].second = mp[v[i].second];
  }
  vvi be(id), ed(id);
  for(int i=0;i<(3*n);++i) {
    be[v[i].first].push_back(i);
    ed[v[i].second].push_back(i);
  }
  int mi = INF;
  for(int i=0;i<(id);++i) {
    vector<bool> sel(n);
    vector<int> now;
    int cnt = 0;
    int nowbeg = i;
    for(int j=(i);j<(id);++j) {
      for(int k=0;k<((int)(be[j].size()));++k) {
        now.push_back(be[j][k]);
      }
      bool ok = false;
      for(int k=0;k<((int)(ed[j].size()));++k) {
        int idx = ed[j][k];
        if(!sel[idx%n] && v[idx].first >= nowbeg) {
          ok = true;
          break;
        }
      }
      if(ok) {
        nowbeg = j+1;
        cnt++;
        for(auto &e: now) {
          sel[e%n] = true;
        }
        now.clear();
      }
    }
    bool ok = true;
    for(int j=0;j<(n);++j) ok &= sel[j];
    if(ok) {
      chmin(mi, cnt);
    }
  }
  cout << mi << endl;
}


### 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;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using P = pair<int, int>;
const double eps = 1e-8;
const ll MOD = 1000000007;
const int INF = INT_MAX / 2;
const ll LINF = LLONG_MAX / 2;
template <typename T1, typename T2>
bool chmax(T1 &a, const T2 &b) {
  if(a < b) {a = b; return true;}
  return false;
}
template <typename T1, typename T2>
bool chmin(T1 &a, const T2 &b) {
  if(a > b) {a = b; return true;}
  return false;
}
template<typename T1, typename T2>
ostream& operator<<(ostream &os, const pair<T1, T2> p) {
  os << p.first << ":" << p.second;
  return os;
}
template<class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  for(int i=0;i<((int)(v.size()));++i) {
    if(i) os << " ";
    os << v[i];
  }
  return os;
}
P pos0(int i, int j, int w, int d) {
  int mi = min(i, j);
  return make_pair(i-mi, j-mi);
}
P pos1(int i, int j, int w, int d) {
  int mi = min(i, w-j);
  return make_pair(i-mi, j+mi);
}
P pos2(int i, int j, int w, int d) {
  int mi = min(d-i, w-j);
  return make_pair(i+mi, j+mi);
}
P pos3(int i, int j, int w, int d) {
  int mi = min(d-i, j);
  return make_pair(i+mi, j-mi);
}
int rect_to_range(int r, int c, int w, int d) {
  if(r == 0 && c != w) {
    return c;
  } else if(c == w && r != d) {
    return w + r;
  } else if(r == d && c != 0) {
    return w + d + (w-c);
  } else {
    return 2 * w + d + (d-r);
  }
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  int n, w, d; cin >> n >> w >> d;
  vector<P> v(3*n);
  for(int i=0;i<(n);++i) {
    int x, y; char f; cin >> x >> y >> f;
    P l, r;
    if(f == 'S') {
      l = pos0(y, x, w, d);
      r = pos1(y, x, w, d);
    } else if(f == 'E') {
      l = pos1(y, x, w, d);
      r = pos2(y, x, w, d);
    } else if(f == 'N') {
      l = pos2(y, x, w, d);
      r = pos3(y, x, w, d);
    } else {
      l = pos3(y, x, w, d);
      r = pos0(y, x, w, d);
    }
    v[i].first = rect_to_range(l.first, l.second, w, d);
    v[i].second = rect_to_range(r.first, r.second, w, d);
    if(v[i].first > v[i].second) v[i].second += 2 * (w + d);
  }
  for(int i=(n);i<(2*n);++i) {
    v[i].first = v[i-n].first + 2*(w+d);
    v[i].second = v[i-n].second + 2*(w+d);
  }
  for(int i=(2*n);i<(3*n);++i) {
    v[i].first = v[i-n].first + 2*(w+d);
    v[i].second = v[i-n].second + 2*(w+d);
  }
  set<int> st;
  for(int i=0;i<(3*n);++i) {
    st.insert(v[i].first);
    st.insert(v[i].second);
  }
  map<int, int> mp;
  int id = 0;
  for(auto &e: st) {
    mp[e] = id;
    id++;
  }
  for(int i=0;i<(3*n);++i) {
    v[i].first = mp[v[i].first];
    v[i].second = mp[v[i].second];
  }
  vvi be(id), ed(id);
  for(int i=0;i<(3*n);++i) {
    be[v[i].first].push_back(i);
    ed[v[i].second].push_back(i);
  }
  int mi = INF;
  for(int i=0;i<(id);++i) {
    vector<bool> sel(n);
    vector<int> now;
    int cnt = 0;
    int nowbeg = i;
    for(int j=(i);j<(id);++j) {
      for(int k=0;k<((int)(be[j].size()));++k) {
        now.push_back(be[j][k]);
      }
      bool ok = false;
      for(int k=0;k<((int)(ed[j].size()));++k) {
        int idx = ed[j][k];
        if(!sel[idx%n] && v[idx].first >= nowbeg) {
          ok = true;
          break;
        }
      }
      if(ok) {
        nowbeg = j+1;
        cnt++;
        for(auto &e: now) {
          sel[e%n] = true;
        }
        now.clear();
      }
    }
    bool ok = true;
    for(int j=0;j<(n);++j) ok &= sel[j];
    if(ok) {
      chmin(mi, cnt);
    }
  }
  cout << mi << endl;
}


```