#include <bits/stdc++.h>
using namespace std;
using itn = int;
using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using ii = pair<int, int>;
using iii = pair<int, ii>;
using dijque = priority_queue<ii, vector<ii>, greater<ii>>;
using graph = vector<vector<int>>;
using wgraph = vector<vector<ii>>;
const ll MODULE = 1000000007;
ll modm(ll a, ll b) { return (a * b) % MODULE; }
ll modp(ll a, ll b) { return (a + b) % MODULE; }
ll modmi(ll a, ll b) { return (a - b) % MODULE; }
ll moddiv(ll a, ll b) { return (a / b) % MODULE; }
void bubble_sort(vi *a) {
  for (int i = 0; i < (*a).size(); i++) {
    for (int j = i + 1; j < (*a).size(); j++) {
      if ((*a)[i] > (*a)[j]) (*a)[i] ^= ((*a)[j] ^= ((*a)[i] ^= (*a)[j]));
    }
  }
}
bool binary_search(vi a, int v) {
  int l = 0, r = a.size() - 1, m = (l + r) / 2;
  while (l <= r) {
    if (a[m] == v) return true;
    if (a[m] > v)
      r = m - 1;
    else
      l = m + 1;
    m = (l + r) / 2;
  }
  return false;
}
int gcd(int a, int b) { return a == 0 || b == 0 ? a ^ b : gcd(b, a % b); }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
struct segtree {
  int size;
  vector<int> tree;
  void init(int n) {
    size = 1;
    while (size < n) size *= 2;
    tree.assign(2 * size - 1, 0);
  }
  void build(vi a, int x, int lx, int rx) {
    if (rx - lx == 1) {
      if (lx < a.size()) tree[x] = a[lx];
    } else {
      int m = (lx + rx) / 2;
      build(a, 2 * x + 1, lx, m);
      build(a, 2 * x + 2, m, rx);
      tree[x] = tree[2 * x + 1] + tree[2 * x + 2];
    }
  }
  void build(vi a) {
    init(a.size());
    build(a, 0, 0, size);
  }
  void set(int i, int v, int x, int lx, int rx) {
    if (rx - lx == 1)
      tree[x] = v;
    else {
      int m = (lx + rx) / 2;
      if (i < m)
        set(i, v, 2 * x + 1, lx, m);
      else
        set(i, v, 2 * x + 2, m, rx);
      tree[x] = tree[2 * x + 1] + tree[2 * x + 2];
    }
  }
  void set(int i, int v) { set(i, v, 0, 0, size); }
  int accumulate(int l, int r, int x, int lx, int rx) {
    if (l >= rx || r <= lx)
      return 0;
    else if (lx >= l && rx <= r)
      return tree[x];
    else {
      int m = (lx + rx) / 2;
      return accumulate(l, r, 2 * x + 1, lx, m) +
             accumulate(l, r, 2 * x + 2, m, rx);
    }
  }
  int accumulate(int l, int r) { return accumulate(l, r, 0, 0, size); }
};
class dsu {
 public:
  vector<int> p;
  vector<int> sizes;
  int n;
  dsu(int _n) : n(_n) {
    p.resize(n);
    iota(p.begin(), p.end(), 0);
    sizes = vector<int>(n, 0);
  }
  inline int get(int u) { return p[u] == u ? u : (p[u] = get(p[u])); }
  inline int size(int u) { return sizes[get(u)]; }
  inline bool unite(int u, int v) {
    u = get(u);
    v = get(v);
    if (u != v) {
      p[u] = v;
      sizes[v] += sizes[u];
      return true;
    }
    return false;
  }
};
int palindromity(string s, int l, int r) {
  if (l == r)
    return 1;
  else if (l + 1 == r)
    return s[l] == s[r] ? 2 : 1;
  else if (s[l] == s[r])
    return 2 + palindromity(s, l + 1, r - 1);
  else
    return max(palindromity(s, l, r - 1), palindromity(s, l + 1, r));
}
int palindromity(string s) { return palindromity(s, 0, s.size() - 1); }
template <typename T1, typename T2>
void unp(pair<T1, T2> p, T1 *f, T2 *s) {
  (*f) = p.first;
  (*s) = p.second;
}
template <typename T1, typename T2, typename T3>
void unpp(pair<T1, pair<T2, T3>> p, T1 *f, T2 *s, T3 *t) {
  (*f) = p.first;
  (*s) = p.second.first;
  (*t) = p.second.second;
}
graph g;
wgraph wg;
vi states, colors, paths, ts;
vi ford_bellman(int s) {
  vi res(wg.size(), 1000000000);
  res[s] = 0;
  for (int i = 0; i < wg.size() - 1; i++) {
    for (int u = 0; u < wg.size(); u++) {
      for (int j = 0; j < wg[u].size(); j++) {
        int to, w;
        unp(wg[u][j], &to, &w);
        res[to] = min(res[to], res[u] + w);
      }
    }
  }
  return res;
}
void dfs(int u) {
  states[u] = 1;
  for (int i = 0; i < g[u].size(); i++) {
    int v = g[u][i];
    if (states[v] == 0) dfs(v);
  }
}
void topological_sort(int u) {
  states[u] = 1;
  for (int i = 0; i < g[u].size(); i++) {
    int v = g[u][i];
    if (states[v] == 0) dfs(v);
  }
  ts.push_back(u);
}
void bfs(int s) {
  queue<int> q;
  q.push(s);
  states = vi(g.size(), 0);
  states[s] = 1;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = 0; i < g[u].size(); i++) {
      int v = g[u][i];
      if (states[v] == 0) {
        states[v] = 1;
        q.push(v);
      }
    }
  }
}
bool isBipartite() {
  bool bipartite = true;
  states = vi(g.size(), 0);
  colors = vi(g.size(), 0);
  for (int s = 0; s < g.size(); s++) {
    if (states[s] == 0) {
      queue<int> q;
      q.push(s);
      states[s] = 1;
      while (!q.empty() && bipartite) {
        int u = q.front();
        q.pop();
        for (int i = 0; i < g[u].size(); i++) {
          int v = g[u][i];
          if (states[v] == 0) {
            states[v] = 1;
            colors[v] = !colors[u];
            q.push(v);
          } else if (states[v] == 1 && colors[v] == colors[u]) {
            bipartite = false;
            break;
          }
        }
      }
    }
  }
  return bipartite;
}
vi sssp_bfs(int s, int d) {
  vi res;
  queue<int> q;
  q.push(s);
  states = vi(g.size(), 0);
  paths = vi(g.size(), -1);
  states[s] = 1;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = 0; i < g[u].size(); i++) {
      int v = g[u][i];
      if (states[v] == 0) {
        states[v] = 1;
        paths[v] = u;
        q.push(v);
      }
    }
  }
  if (paths[d] == -1) return res;
  while (d != s) {
    res.push_back(d);
    d = paths[d];
  }
  res.push_back(s);
  reverse(res.begin(), res.end());
  return res;
}
int cruscal(vector<iii> el, int n) {
  sort(el.begin(), el.end());
  dsu d(n);
  int min_cost = 0;
  for (int i = 0; i < el.size(); i++) {
    int u, v, w;
    unpp(el[i], &w, &u, &v);
    if (d.get(u) != d.get(v)) {
      min_cost += w;
      d.unite(u, v);
    }
  }
  return min_cost;
}
vi dijkstra(int s) {
  vi dist(wg.size(), 1000000000);
  priority_queue<ii, vector<ii>, greater<ii>> q;
  q.push({0, s});
  dist[s] = 0;
  while (!q.empty()) {
    int d, u;
    unp(q.top(), &d, &u);
    q.pop();
    if (dist[u] < d) continue;
    for (int i = 0; i < wg[u].size(); i++) {
      int v, w;
      unp(wg[u][i], &v, &w);
      if (dist[v] <= dist[u] + w) continue;
      dist[v] = dist[u] + w;
      q.push({dist[v], v});
    }
  }
  return dist;
}
graph floyd_warshall(graph adj) {
  for (int k = 0; k < g.size(); k++)
    for (int i = 0; i < g.size(); i++)
      for (int j = 0; j < g.size(); j++)
        adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
  return adj;
}
vi read_vi(int n) {
  vi v(n, 0);
  for (int i = 0; i < n; i += 1) cin >> v[i];
  return v;
}
vll read_vll(int n) {
  vll v(n, 0);
  for (int i = 0; i < n; i += 1) cin >> v[i];
  return v;
}
void print(vi v) {
  for (int i = 0; i < v.size(); i += 1) {
    if (i != 0) cout << " ";
    cout << v[i];
  }
  cout << endl;
}
void print(vll v) {
  for (int i = 0; i < v.size(); i += 1) {
    if (i != 0) cout << " ";
    cout << v[i];
  }
  cout << endl;
}
ll sum_all(int n) { return n % 2 == 0 ? n / 2 * (n + 1) : n * ((n + 1) / 2); }
ll sum_all(ll n) { return n % 2 == 0 ? n / 2 * (n + 1) : n * ((n + 1) / 2); }
int main() {
  int n, m;
  cin >> n >> m;
  int l = 0, r = n - 1;
  bool stillNormal = true;
  for (int i = 0; i < m; i++) {
    string un, lr;
    int pos;
    cin >> un >> un >> lr >> un >> pos;
    if (stillNormal) {
      if (lr[0] == 'l')
        r = min(r, pos - 2);
      else
        l = max(pos, l);
      if (l > r || l < 0 || r < 0) stillNormal = false;
    }
  }
  cout << (stillNormal ? r - l + 1 : -1) << endl;
  return 0;
}

### Prompt

Please provide a Cpp coded solution to the problem described below:

<image>

One morning the Cereal Guy found out that all his cereal flakes were gone. He found a note instead of them. It turned out that his smart roommate hid the flakes in one of n boxes. The boxes stand in one row, they are numbered from 1 to n from the left to the right. The roommate left hints like "Hidden to the left of the i-th box" ("To the left of i"), "Hidden to the right of the i-th box" ("To the right of i"). Such hints mean that there are no flakes in the i-th box as well. The Cereal Guy wants to know the minimal number of boxes he necessarily needs to check to find the flakes considering all the hints. Or he wants to find out that the hints are contradictory and the roommate lied to him, that is, no box has the flakes.

Input

The first line contains two integers n and m (1 ≤ n ≤ 1000, 0 ≤ m ≤ 1000) which represent the number of boxes and the number of hints correspondingly. Next m lines contain hints like "To the left of i" and "To the right of i", where i is integer (1 ≤ i ≤ n). The hints may coincide.

Output

The answer should contain exactly one integer — the number of boxes that should necessarily be checked or "-1" if the hints are contradictory.

Examples

Input

2 1
To the left of 2


Output

1


Input

3 2
To the right of 1
To the right of 2


Output

1


Input

3 1
To the left of 3


Output

2


Input

3 2
To the left of 2
To the right of 1


Output

-1

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
using itn = int;
using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using ii = pair<int, int>;
using iii = pair<int, ii>;
using dijque = priority_queue<ii, vector<ii>, greater<ii>>;
using graph = vector<vector<int>>;
using wgraph = vector<vector<ii>>;
const ll MODULE = 1000000007;
ll modm(ll a, ll b) { return (a * b) % MODULE; }
ll modp(ll a, ll b) { return (a + b) % MODULE; }
ll modmi(ll a, ll b) { return (a - b) % MODULE; }
ll moddiv(ll a, ll b) { return (a / b) % MODULE; }
void bubble_sort(vi *a) {
  for (int i = 0; i < (*a).size(); i++) {
    for (int j = i + 1; j < (*a).size(); j++) {
      if ((*a)[i] > (*a)[j]) (*a)[i] ^= ((*a)[j] ^= ((*a)[i] ^= (*a)[j]));
    }
  }
}
bool binary_search(vi a, int v) {
  int l = 0, r = a.size() - 1, m = (l + r) / 2;
  while (l <= r) {
    if (a[m] == v) return true;
    if (a[m] > v)
      r = m - 1;
    else
      l = m + 1;
    m = (l + r) / 2;
  }
  return false;
}
int gcd(int a, int b) { return a == 0 || b == 0 ? a ^ b : gcd(b, a % b); }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
struct segtree {
  int size;
  vector<int> tree;
  void init(int n) {
    size = 1;
    while (size < n) size *= 2;
    tree.assign(2 * size - 1, 0);
  }
  void build(vi a, int x, int lx, int rx) {
    if (rx - lx == 1) {
      if (lx < a.size()) tree[x] = a[lx];
    } else {
      int m = (lx + rx) / 2;
      build(a, 2 * x + 1, lx, m);
      build(a, 2 * x + 2, m, rx);
      tree[x] = tree[2 * x + 1] + tree[2 * x + 2];
    }
  }
  void build(vi a) {
    init(a.size());
    build(a, 0, 0, size);
  }
  void set(int i, int v, int x, int lx, int rx) {
    if (rx - lx == 1)
      tree[x] = v;
    else {
      int m = (lx + rx) / 2;
      if (i < m)
        set(i, v, 2 * x + 1, lx, m);
      else
        set(i, v, 2 * x + 2, m, rx);
      tree[x] = tree[2 * x + 1] + tree[2 * x + 2];
    }
  }
  void set(int i, int v) { set(i, v, 0, 0, size); }
  int accumulate(int l, int r, int x, int lx, int rx) {
    if (l >= rx || r <= lx)
      return 0;
    else if (lx >= l && rx <= r)
      return tree[x];
    else {
      int m = (lx + rx) / 2;
      return accumulate(l, r, 2 * x + 1, lx, m) +
             accumulate(l, r, 2 * x + 2, m, rx);
    }
  }
  int accumulate(int l, int r) { return accumulate(l, r, 0, 0, size); }
};
class dsu {
 public:
  vector<int> p;
  vector<int> sizes;
  int n;
  dsu(int _n) : n(_n) {
    p.resize(n);
    iota(p.begin(), p.end(), 0);
    sizes = vector<int>(n, 0);
  }
  inline int get(int u) { return p[u] == u ? u : (p[u] = get(p[u])); }
  inline int size(int u) { return sizes[get(u)]; }
  inline bool unite(int u, int v) {
    u = get(u);
    v = get(v);
    if (u != v) {
      p[u] = v;
      sizes[v] += sizes[u];
      return true;
    }
    return false;
  }
};
int palindromity(string s, int l, int r) {
  if (l == r)
    return 1;
  else if (l + 1 == r)
    return s[l] == s[r] ? 2 : 1;
  else if (s[l] == s[r])
    return 2 + palindromity(s, l + 1, r - 1);
  else
    return max(palindromity(s, l, r - 1), palindromity(s, l + 1, r));
}
int palindromity(string s) { return palindromity(s, 0, s.size() - 1); }
template <typename T1, typename T2>
void unp(pair<T1, T2> p, T1 *f, T2 *s) {
  (*f) = p.first;
  (*s) = p.second;
}
template <typename T1, typename T2, typename T3>
void unpp(pair<T1, pair<T2, T3>> p, T1 *f, T2 *s, T3 *t) {
  (*f) = p.first;
  (*s) = p.second.first;
  (*t) = p.second.second;
}
graph g;
wgraph wg;
vi states, colors, paths, ts;
vi ford_bellman(int s) {
  vi res(wg.size(), 1000000000);
  res[s] = 0;
  for (int i = 0; i < wg.size() - 1; i++) {
    for (int u = 0; u < wg.size(); u++) {
      for (int j = 0; j < wg[u].size(); j++) {
        int to, w;
        unp(wg[u][j], &to, &w);
        res[to] = min(res[to], res[u] + w);
      }
    }
  }
  return res;
}
void dfs(int u) {
  states[u] = 1;
  for (int i = 0; i < g[u].size(); i++) {
    int v = g[u][i];
    if (states[v] == 0) dfs(v);
  }
}
void topological_sort(int u) {
  states[u] = 1;
  for (int i = 0; i < g[u].size(); i++) {
    int v = g[u][i];
    if (states[v] == 0) dfs(v);
  }
  ts.push_back(u);
}
void bfs(int s) {
  queue<int> q;
  q.push(s);
  states = vi(g.size(), 0);
  states[s] = 1;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = 0; i < g[u].size(); i++) {
      int v = g[u][i];
      if (states[v] == 0) {
        states[v] = 1;
        q.push(v);
      }
    }
  }
}
bool isBipartite() {
  bool bipartite = true;
  states = vi(g.size(), 0);
  colors = vi(g.size(), 0);
  for (int s = 0; s < g.size(); s++) {
    if (states[s] == 0) {
      queue<int> q;
      q.push(s);
      states[s] = 1;
      while (!q.empty() && bipartite) {
        int u = q.front();
        q.pop();
        for (int i = 0; i < g[u].size(); i++) {
          int v = g[u][i];
          if (states[v] == 0) {
            states[v] = 1;
            colors[v] = !colors[u];
            q.push(v);
          } else if (states[v] == 1 && colors[v] == colors[u]) {
            bipartite = false;
            break;
          }
        }
      }
    }
  }
  return bipartite;
}
vi sssp_bfs(int s, int d) {
  vi res;
  queue<int> q;
  q.push(s);
  states = vi(g.size(), 0);
  paths = vi(g.size(), -1);
  states[s] = 1;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = 0; i < g[u].size(); i++) {
      int v = g[u][i];
      if (states[v] == 0) {
        states[v] = 1;
        paths[v] = u;
        q.push(v);
      }
    }
  }
  if (paths[d] == -1) return res;
  while (d != s) {
    res.push_back(d);
    d = paths[d];
  }
  res.push_back(s);
  reverse(res.begin(), res.end());
  return res;
}
int cruscal(vector<iii> el, int n) {
  sort(el.begin(), el.end());
  dsu d(n);
  int min_cost = 0;
  for (int i = 0; i < el.size(); i++) {
    int u, v, w;
    unpp(el[i], &w, &u, &v);
    if (d.get(u) != d.get(v)) {
      min_cost += w;
      d.unite(u, v);
    }
  }
  return min_cost;
}
vi dijkstra(int s) {
  vi dist(wg.size(), 1000000000);
  priority_queue<ii, vector<ii>, greater<ii>> q;
  q.push({0, s});
  dist[s] = 0;
  while (!q.empty()) {
    int d, u;
    unp(q.top(), &d, &u);
    q.pop();
    if (dist[u] < d) continue;
    for (int i = 0; i < wg[u].size(); i++) {
      int v, w;
      unp(wg[u][i], &v, &w);
      if (dist[v] <= dist[u] + w) continue;
      dist[v] = dist[u] + w;
      q.push({dist[v], v});
    }
  }
  return dist;
}
graph floyd_warshall(graph adj) {
  for (int k = 0; k < g.size(); k++)
    for (int i = 0; i < g.size(); i++)
      for (int j = 0; j < g.size(); j++)
        adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
  return adj;
}
vi read_vi(int n) {
  vi v(n, 0);
  for (int i = 0; i < n; i += 1) cin >> v[i];
  return v;
}
vll read_vll(int n) {
  vll v(n, 0);
  for (int i = 0; i < n; i += 1) cin >> v[i];
  return v;
}
void print(vi v) {
  for (int i = 0; i < v.size(); i += 1) {
    if (i != 0) cout << " ";
    cout << v[i];
  }
  cout << endl;
}
void print(vll v) {
  for (int i = 0; i < v.size(); i += 1) {
    if (i != 0) cout << " ";
    cout << v[i];
  }
  cout << endl;
}
ll sum_all(int n) { return n % 2 == 0 ? n / 2 * (n + 1) : n * ((n + 1) / 2); }
ll sum_all(ll n) { return n % 2 == 0 ? n / 2 * (n + 1) : n * ((n + 1) / 2); }
int main() {
  int n, m;
  cin >> n >> m;
  int l = 0, r = n - 1;
  bool stillNormal = true;
  for (int i = 0; i < m; i++) {
    string un, lr;
    int pos;
    cin >> un >> un >> lr >> un >> pos;
    if (stillNormal) {
      if (lr[0] == 'l')
        r = min(r, pos - 2);
      else
        l = max(pos, l);
      if (l > r || l < 0 || r < 0) stillNormal = false;
    }
  }
  cout << (stillNormal ? r - l + 1 : -1) << endl;
  return 0;
}

```