#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:512000000")
using namespace std;
void solve(bool);
void precalc();
clock_t start;
int testNumber = 1;
bool todo = true;
int main() {
  start = clock();
  int t = 1;
  cout.sync_with_stdio(0);
  cin.tie(0);
  precalc();
  cout.precision(10);
  cout << fixed;
  int testNum = 1;
  while (t--) {
    solve(true);
    ++testNumber;
  }
  cout.flush();
  return 0;
}
template <typename T>
T binpow(T q, T w, T mod) {
  if (!w) return 1 % mod;
  if (w & 1) return q * 1LL * binpow(q, w - 1, mod) % mod;
  return binpow(q * 1LL * q % mod, w / 2, mod);
}
template <typename T>
T gcd(T q, T w) {
  while (w) {
    q %= w;
    swap(q, w);
  }
  return q;
}
template <typename T>
T lcm(T q, T w) {
  return q / gcd(q, w) * w;
}
void precalc() {}
int get_prev_by_parity(int cur, int par) {
  if ((cur + par) & 1) {
    return cur - 1;
  } else {
    return cur - 2;
  }
}
struct Event {
  int l, r;
  int sign;
};
const int shift = 1 << 17;
const int INF = (int)1e9;
struct Node {
  int min;
  int cnt_mins;
  long long sum_mins;
  int push_add;
  Node() : min(INF), sum_mins(0), push_add(0) {}
};
Node tree[2 * shift];
void push(int v) {
  Node& cur = tree[v];
  for (int h = 0; h < 2; ++h) {
    Node& child = tree[2 * v + h];
    child.push_add += cur.push_add;
    child.min += cur.push_add;
  }
  cur.push_add = 0;
}
Node merge(const Node& l, const Node& r) {
  Node res = l;
  if (res.min > r.min) {
    res = r;
  } else if (res.min == r.min) {
    res.sum_mins += r.sum_mins;
    res.cnt_mins += r.cnt_mins;
  }
  res.push_add = 0;
  return res;
}
Node rmq(int v, int tl, int tr, int l, int r) {
  if (tr <= l || r <= tl) {
    return Node();
  }
  if (l <= tl && tr <= r) {
    return tree[v];
  }
  push(v);
  int tm = (tl + tr) / 2;
  Node ans = merge(rmq(2 * v, tl, tm, l, r), rmq(2 * v + 1, tm, tr, l, r));
  return ans;
}
Node get_min(int l, int r) { return rmq(1, 0, shift, l, r); }
void modify(int v, int tl, int tr, int l, int r, int val) {
  if (tr <= l || r <= tl) {
    return;
  }
  if (l <= tl && tr <= r) {
    tree[v].push_add += val;
    tree[v].min += val;
    return;
  }
  push(v);
  int tm = (tl + tr) / 2;
  modify(2 * v, tl, tm, l, r, val);
  modify(2 * v + 1, tm, tr, l, r, val);
  tree[v] = merge(tree[2 * v], tree[2 * v + 1]);
}
void update(int l, int r, int val) { return modify(1, 0, shift, l, r, val); }
void build(int v, int tl, int tr, int m, int par) {
  if (tl >= m) {
    return;
  }
  if (tl + 1 == tr) {
    tree[v].min = 0;
    tree[v].cnt_mins = 1;
    tree[v].sum_mins = tl * 2 + par;
    tree[v].push_add = 0;
    return;
  }
  int tm = (tl + tr) / 2;
  build(2 * v, tl, tm, m, par);
  build(2 * v + 1, tm, tr, m, par);
  tree[v] = merge(tree[2 * v], tree[2 * v + 1]);
}
void build(int m, int par) { return build(1, 0, shift, m, par); }
void solve(bool read) {
  int n, m;
  if (read) {
    cin >> n >> m;
  } else {
    n = 200000;
    m = 200000;
  }
  vector<pair<int, int>> a(n);
  for (int i = 0; i < n; ++i) {
    if (read) {
      cin >> a[i].first >> a[i].second;
      --a[i].first;
      --a[i].second;
    } else {
      a[i].first = 2 * (rand() % (m / 2));
      a[i].second = 2 * (rand() % (m / 2)) + 1;
      if (a[i].second < a[i].first) {
        swap(a[i].first, a[i].second);
      }
    }
  }
  vector<vector<Event>> events(m + 1);
  long long res = 0;
  double sum_time = 0;
  for (int par_a = 0; par_a < 2; ++par_a) {
    for (int par_b = 0; par_b < 2; ++par_b) {
      for (int i = 0; i < m; ++i) events[i].clear();
      for (int i = 0; i < n; ++i) {
        int change = get_prev_by_parity(a[i].first, par_a) + 2;
        if ((a[i].first + par_b) & 1) {
          if ((a[i].first + a[i].second) & 1) {
            events[par_a].push_back({a[i].first, m - 1, 1});
            events[change].push_back({a[i].first, m - 1, -1});
          } else {
            events[par_a].push_back({a[i].first, a[i].second, 1});
            events[change].push_back({a[i].first, a[i].second, -1});
          }
        } else if ((a[i].first + a[i].second) & 1) {
          events[par_a].push_back({a[i].second + 1, m - 1, 1});
          events[change].push_back({a[i].second + 1, m - 1, -1});
        }
        int next_change = get_prev_by_parity(a[i].second, par_a) + 2;
        if ((par_b + par_a) & 1) {
          if ((a[i].second + par_a) & 1) {
            events[change].push_back({a[i].first, m - 1, 1});
            events[next_change].push_back({a[i].first, m - 1, -1});
          } else {
            events[change].push_back({a[i].first, a[i].second, 1});
            events[next_change].push_back({a[i].first, a[i].second, -1});
          }
        } else if ((a[i].second + par_a) & 1) {
          events[change].push_back({a[i].second + 1, m - 1, 1});
          events[next_change].push_back({a[i].second + 1, m - 1, -1});
        }
      }
      for (int i = 0; i < events.size(); ++i) {
        for (auto& e : events[i]) {
          if ((e.l + par_b) & 1) {
            ++e.l;
          }
          if ((e.r + par_b) & 1) {
            --e.r;
          }
          e.l >>= 1;
          e.r >>= 1;
        }
      }
      int size = (m + 1 - par_b) >> 1;
      build(size, par_b);
      for (int i = 0; i < m; ++i) {
        if ((i + par_a) % 2) {
          assert(events[i].empty());
          continue;
        }
        for (auto& e : events[i]) {
          update(e.l, e.r + 1, e.sign);
        }
        int min_index = (get_prev_by_parity(i, par_b) + 2) / 2;
        Node cur_sum = get_min(min_index, size);
        if (cur_sum.min == 0) {
          long long sum_add =
              cur_sum.sum_mins - cur_sum.cnt_mins * 1LL * i + cur_sum.cnt_mins;
          res += sum_add;
        }
      }
    }
  }
  vector<int> pref_add(m + 1);
  for (int i = 0; i < n; ++i) {
    ++pref_add[a[i].first];
    --pref_add[a[i].second + 1];
  }
  for (int i = 0; i < m; ++i) {
    pref_add[i + 1] += pref_add[i];
  }
  for (int i = 0; i < m;) {
    if (pref_add[i]) {
      ++i;
      continue;
    }
    int j = i;
    while (j < m && pref_add[j] == 0) {
      ++j;
    }
    int len = j - i;
    for (int r = 1; r <= len; ++r) {
      res -= (len - r + 1) * 1LL * r;
    }
    i = j;
  }
  cout << res << endl;
}

### Prompt

Develop a solution in CPP to the problem described below:

Butler Ostin wants to show Arkady that rows of odd number of fountains are beautiful, while rows of even number of fountains are not.

The butler wants to show Arkady n gardens. Each garden is a row of m cells, the i-th garden has one fountain in each of the cells between li and ri inclusive, and there are no more fountains in that garden. The issue is that some of the gardens contain even number of fountains, it is wrong to show them to Arkady.

Ostin wants to choose two integers a ≤ b and show only part of each of the gardens that starts at cell a and ends at cell b. Of course, only such segments suit Ostin that each garden has either zero or odd number of fountains on this segment. Also, it is necessary that at least one garden has at least one fountain on the segment from a to b.

Help Ostin to find the total length of all such segments, i.e. sum up the value (b - a + 1) for each suitable pair (a, b).

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 2·105) — the number of gardens and the length of each garden.

n lines follow. The i-th of these lines contains two integers li and ri (1 ≤ li ≤ ri ≤ m) — the bounds of the segment that contains fountains in the i-th garden.

Output

Print one integer: the total length of all suitable segments.

Examples

Input

1 5
2 4


Output

23


Input

3 6
2 4
3 6
4 4


Output

19

Note

In the first example the following pairs suit Ostin: (a, b): (1, 2), (1, 4), (1, 5), (2, 2), (2, 4), (2, 5), (3, 3), (4, 4), (4, 5).

In the second example the following pairs suit Ostin: (a, b): (1, 2), (1, 5), (2, 2), (2, 5), (3, 3), (4, 4), (4, 6), (5, 5), (6, 6).

### Response

```cpp
#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:512000000")
using namespace std;
void solve(bool);
void precalc();
clock_t start;
int testNumber = 1;
bool todo = true;
int main() {
  start = clock();
  int t = 1;
  cout.sync_with_stdio(0);
  cin.tie(0);
  precalc();
  cout.precision(10);
  cout << fixed;
  int testNum = 1;
  while (t--) {
    solve(true);
    ++testNumber;
  }
  cout.flush();
  return 0;
}
template <typename T>
T binpow(T q, T w, T mod) {
  if (!w) return 1 % mod;
  if (w & 1) return q * 1LL * binpow(q, w - 1, mod) % mod;
  return binpow(q * 1LL * q % mod, w / 2, mod);
}
template <typename T>
T gcd(T q, T w) {
  while (w) {
    q %= w;
    swap(q, w);
  }
  return q;
}
template <typename T>
T lcm(T q, T w) {
  return q / gcd(q, w) * w;
}
void precalc() {}
int get_prev_by_parity(int cur, int par) {
  if ((cur + par) & 1) {
    return cur - 1;
  } else {
    return cur - 2;
  }
}
struct Event {
  int l, r;
  int sign;
};
const int shift = 1 << 17;
const int INF = (int)1e9;
struct Node {
  int min;
  int cnt_mins;
  long long sum_mins;
  int push_add;
  Node() : min(INF), sum_mins(0), push_add(0) {}
};
Node tree[2 * shift];
void push(int v) {
  Node& cur = tree[v];
  for (int h = 0; h < 2; ++h) {
    Node& child = tree[2 * v + h];
    child.push_add += cur.push_add;
    child.min += cur.push_add;
  }
  cur.push_add = 0;
}
Node merge(const Node& l, const Node& r) {
  Node res = l;
  if (res.min > r.min) {
    res = r;
  } else if (res.min == r.min) {
    res.sum_mins += r.sum_mins;
    res.cnt_mins += r.cnt_mins;
  }
  res.push_add = 0;
  return res;
}
Node rmq(int v, int tl, int tr, int l, int r) {
  if (tr <= l || r <= tl) {
    return Node();
  }
  if (l <= tl && tr <= r) {
    return tree[v];
  }
  push(v);
  int tm = (tl + tr) / 2;
  Node ans = merge(rmq(2 * v, tl, tm, l, r), rmq(2 * v + 1, tm, tr, l, r));
  return ans;
}
Node get_min(int l, int r) { return rmq(1, 0, shift, l, r); }
void modify(int v, int tl, int tr, int l, int r, int val) {
  if (tr <= l || r <= tl) {
    return;
  }
  if (l <= tl && tr <= r) {
    tree[v].push_add += val;
    tree[v].min += val;
    return;
  }
  push(v);
  int tm = (tl + tr) / 2;
  modify(2 * v, tl, tm, l, r, val);
  modify(2 * v + 1, tm, tr, l, r, val);
  tree[v] = merge(tree[2 * v], tree[2 * v + 1]);
}
void update(int l, int r, int val) { return modify(1, 0, shift, l, r, val); }
void build(int v, int tl, int tr, int m, int par) {
  if (tl >= m) {
    return;
  }
  if (tl + 1 == tr) {
    tree[v].min = 0;
    tree[v].cnt_mins = 1;
    tree[v].sum_mins = tl * 2 + par;
    tree[v].push_add = 0;
    return;
  }
  int tm = (tl + tr) / 2;
  build(2 * v, tl, tm, m, par);
  build(2 * v + 1, tm, tr, m, par);
  tree[v] = merge(tree[2 * v], tree[2 * v + 1]);
}
void build(int m, int par) { return build(1, 0, shift, m, par); }
void solve(bool read) {
  int n, m;
  if (read) {
    cin >> n >> m;
  } else {
    n = 200000;
    m = 200000;
  }
  vector<pair<int, int>> a(n);
  for (int i = 0; i < n; ++i) {
    if (read) {
      cin >> a[i].first >> a[i].second;
      --a[i].first;
      --a[i].second;
    } else {
      a[i].first = 2 * (rand() % (m / 2));
      a[i].second = 2 * (rand() % (m / 2)) + 1;
      if (a[i].second < a[i].first) {
        swap(a[i].first, a[i].second);
      }
    }
  }
  vector<vector<Event>> events(m + 1);
  long long res = 0;
  double sum_time = 0;
  for (int par_a = 0; par_a < 2; ++par_a) {
    for (int par_b = 0; par_b < 2; ++par_b) {
      for (int i = 0; i < m; ++i) events[i].clear();
      for (int i = 0; i < n; ++i) {
        int change = get_prev_by_parity(a[i].first, par_a) + 2;
        if ((a[i].first + par_b) & 1) {
          if ((a[i].first + a[i].second) & 1) {
            events[par_a].push_back({a[i].first, m - 1, 1});
            events[change].push_back({a[i].first, m - 1, -1});
          } else {
            events[par_a].push_back({a[i].first, a[i].second, 1});
            events[change].push_back({a[i].first, a[i].second, -1});
          }
        } else if ((a[i].first + a[i].second) & 1) {
          events[par_a].push_back({a[i].second + 1, m - 1, 1});
          events[change].push_back({a[i].second + 1, m - 1, -1});
        }
        int next_change = get_prev_by_parity(a[i].second, par_a) + 2;
        if ((par_b + par_a) & 1) {
          if ((a[i].second + par_a) & 1) {
            events[change].push_back({a[i].first, m - 1, 1});
            events[next_change].push_back({a[i].first, m - 1, -1});
          } else {
            events[change].push_back({a[i].first, a[i].second, 1});
            events[next_change].push_back({a[i].first, a[i].second, -1});
          }
        } else if ((a[i].second + par_a) & 1) {
          events[change].push_back({a[i].second + 1, m - 1, 1});
          events[next_change].push_back({a[i].second + 1, m - 1, -1});
        }
      }
      for (int i = 0; i < events.size(); ++i) {
        for (auto& e : events[i]) {
          if ((e.l + par_b) & 1) {
            ++e.l;
          }
          if ((e.r + par_b) & 1) {
            --e.r;
          }
          e.l >>= 1;
          e.r >>= 1;
        }
      }
      int size = (m + 1 - par_b) >> 1;
      build(size, par_b);
      for (int i = 0; i < m; ++i) {
        if ((i + par_a) % 2) {
          assert(events[i].empty());
          continue;
        }
        for (auto& e : events[i]) {
          update(e.l, e.r + 1, e.sign);
        }
        int min_index = (get_prev_by_parity(i, par_b) + 2) / 2;
        Node cur_sum = get_min(min_index, size);
        if (cur_sum.min == 0) {
          long long sum_add =
              cur_sum.sum_mins - cur_sum.cnt_mins * 1LL * i + cur_sum.cnt_mins;
          res += sum_add;
        }
      }
    }
  }
  vector<int> pref_add(m + 1);
  for (int i = 0; i < n; ++i) {
    ++pref_add[a[i].first];
    --pref_add[a[i].second + 1];
  }
  for (int i = 0; i < m; ++i) {
    pref_add[i + 1] += pref_add[i];
  }
  for (int i = 0; i < m;) {
    if (pref_add[i]) {
      ++i;
      continue;
    }
    int j = i;
    while (j < m && pref_add[j] == 0) {
      ++j;
    }
    int len = j - i;
    for (int r = 1; r <= len; ++r) {
      res -= (len - r + 1) * 1LL * r;
    }
    i = j;
  }
  cout << res << endl;
}

```