#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("no-stack-protector")
#pragma GCC target("sse,sse2,ssse3,sse3,sse4,popcnt,avx,mmx,abm,tune=native")
using namespace std;
namespace output {
void __(short x) { cout << x; }
void __(unsigned x) { cout << x; }
void __(int x) { cout << x; }
void __(long long x) { cout << x; }
void __(unsigned long long x) { cout << x; }
void __(double x) { cout << x; }
void __(long double x) { cout << x; }
void __(char x) { cout << x; }
void __(const char* x) { cout << x; }
void __(const string& x) { cout << x; }
void __(bool x) { cout << (x ? "true" : "false"); }
template <class S, class T>
void __(const pair<S, T>& x) {
  __(1 ? "(" : ""), __(x.first), __(1 ? ", " : " "), __(x.second),
      __(1 ? ")" : "");
}
template <class T>
void __(const vector<T>& x) {
  __(1 ? "{" : "");
  bool _ = 0;
  for (const auto& v : x) __(_ ? 1 ? ", " : " " : ""), __(v), _ = 1;
  __(1 ? "}" : "");
}
template <class T>
void __(const set<T>& x) {
  __(1 ? "{" : "");
  bool _ = 0;
  for (const auto& v : x) __(_ ? 1 ? ", " : " " : ""), __(v), _ = 1;
  __(1 ? "}" : "");
}
template <class T>
void __(const multiset<T>& x) {
  __(1 ? "{" : "");
  bool _ = 0;
  for (const auto& v : x) __(_ ? 1 ? ", " : " " : ""), __(v), _ = 1;
  __(1 ? "}" : "");
}
template <class S, class T>
void __(const map<S, T>& x) {
  __(1 ? "{" : "");
  bool _ = 0;
  for (const auto& v : x) __(_ ? 1 ? ", " : " " : ""), __(v), _ = 1;
  __(1 ? "}" : "");
}
void pr() { cout << "\n"; }
template <class S, class... T>
void pr(const S& a, const T&... b) {
  __(a);
  if (sizeof...(b)) __(' ');
  pr(b...);
}
}  // namespace output
using namespace output;
const int MN = 2e5 + 5;
int n, m, i, j, x, y, on[MN], mrk[MN];
pair<int, int> evt[2 * MN], pos[MN];
long long sm[2], ans;
struct dblseg {
  struct idk {
    long long mn, sm, cnt;
  };
  struct nd {
    idk a;
    long long lz;
  } st[2][2 * MN];
  long long n, m;
  void build(int id, int i, int s, int e) {
    if (s < e) {
      build(id, 2 * i, s, (s + e) / 2);
      build(id, 2 * i + 1, (s + e) / 2 + 1, e);
      st[id][i].lz = st[id][i].a.mn = 0;
      st[id][i].a.sm = st[id][2 * i].a.sm + st[id][2 * i + 1].a.sm;
      st[id][i].a.cnt = st[id][2 * i].a.cnt + st[id][2 * i + 1].a.cnt;
    } else if (s == e) {
      st[id][i].a.mn = st[id][i].lz = 0;
      st[id][i].a.sm = 2 * s - 1 + id;
      st[id][i].a.cnt = 1;
    }
  }
  void init(int sz) {
    n = ceil(sz / 2.0);
    m = sz / 2;
    build(0, 1, 1, n);
    build(1, 1, 1, m);
  }
  inline void upd_lz(int id, int i, int s, int e) {
    if (st[id][i].lz) {
      st[id][i].a.mn += st[id][i].lz;
      if (s != e) {
        st[id][2 * i].lz += st[id][i].lz;
        st[id][2 * i + 1].lz += st[id][i].lz;
      }
      st[id][i].lz = 0;
    }
  }
  void upd(int id, int i, int s, int e, int ss, int se, int val) {
    if (ss > se) return;
    upd_lz(id, i, s, e);
    if (s >= ss && e <= se) {
      st[id][i].lz = val;
      upd_lz(id, i, s, e);
    } else {
      if ((s + e) / 2 < ss)
        upd(id, 2 * i + 1, (s + e) / 2 + 1, e, ss, se, val),
            upd_lz(id, 2 * i, s, (s + e) / 2);
      else if ((s + e) / 2 >= se)
        upd(id, 2 * i, s, (s + e) / 2, ss, se, val),
            upd_lz(id, 2 * i + 1, (s + e) / 2 + 1, e);
      else
        upd(id, 2 * i, s, (s + e) / 2, ss, se, val),
            upd(id, 2 * i + 1, (s + e) / 2 + 1, e, ss, se, val);
      st[id][i].a.mn = min(st[id][2 * i].a.mn, st[id][2 * i + 1].a.mn);
      st[id][i].a.sm =
          (st[id][2 * i].a.mn == st[id][i].a.mn ? st[id][2 * i].a.sm : 0) +
          (st[id][2 * i + 1].a.mn == st[id][i].a.mn ? st[id][2 * i + 1].a.sm
                                                    : 0);
      st[id][i].a.cnt =
          (st[id][2 * i].a.mn == st[id][i].a.mn ? st[id][2 * i].a.cnt : 0) +
          (st[id][2 * i + 1].a.mn == st[id][i].a.mn ? st[id][2 * i + 1].a.cnt
                                                    : 0);
    }
  }
  idk qu(int id, int i, int s, int e, int ss, int se) {
    if (ss > se) return {1 << 30, 0, 0};
    upd_lz(id, i, s, e);
    if (s >= ss && e <= se)
      return st[id][i].a;
    else if ((s + e) / 2 < ss)
      return qu(id, 2 * i + 1, (s + e) / 2 + 1, e, ss, se);
    else if ((s + e) / 2 >= se)
      return qu(id, 2 * i, s, (s + e) / 2, ss, se);
    else {
      idk l = qu(id, 2 * i, s, (s + e) / 2, ss, se),
          r = qu(id, 2 * i + 1, (s + e) / 2 + 1, e, ss, se);
      long long mn = min(l.mn, r.mn);
      return {mn, (l.mn == mn ? l.sm : 0) + (r.mn == mn ? r.sm : 0),
              (l.mn == mn ? l.cnt : 0) + (r.mn == mn ? r.cnt : 0)};
    }
  }
  inline void upd(int id, int s, int e, int delta) {
    if (((s + 1) & 1) != id) s++;
    if (((e + 1) & 1) != id) e--;
    if (s > e) return;
    int l = (s - 1) / 2 + 1, r = (e - 1) / 2 + 1;
    upd(id, 1, 1, id ? m : n, l, r, delta);
  }
  inline void upd(int s, int e, int delta) {
    upd(0, s, e, delta);
    upd(1, s, e, delta);
  }
  inline pair<long long, long long> qu(int s, int e) {
    idk a[2];
    for (int i = 0; i < 2; i++) {
      int l = s, r = e;
      if (((l + 1) & 1) != i) l++;
      if (((r + 1) & 1) != i) r--;
      if (l > r) {
        a[i] = {1 << 30, 0, 0};
        continue;
      }
      l = (l - 1) / 2 + 1, r = (r - 1) / 2 + 1;
      a[i] = qu(i, 1, 1, i ? m : n, l, r);
    }
    return make_pair((!a[0].mn ? a[0].sm : 0) + (!a[1].mn ? a[1].sm : 0),
                     (!a[0].mn ? a[0].cnt : 0) + (!a[1].mn ? a[1].cnt : 0));
  }
} seg[2];
int main() {
  for (scanf("%d%d", &n, &m), i = 1; i <= n; i++) {
    scanf("%d%d", &x, &y);
    evt[2 * i - 1] = {x, i};
    evt[2 * i] = {y + 1, i};
    pos[i] = {x, y};
    mrk[x]++;
    mrk[y + 1]--;
  }
  int cnt = 0;
  for (i = 1; i <= m; i++) {
    mrk[i] += mrk[i - 1];
    if (!mrk[i])
      cnt++;
    else
      cnt = 0;
    ans -= 1LL * cnt * (cnt + 1) / 2;
  }
  seg[0].init(m);
  seg[1].init(m);
  sort(evt + 1, evt + 2 * n + 1,
       [](pair<int, int> i, pair<int, int> j) { return i.first < j.first; });
  for (i = j = 1; i <= m; i++) {
    while (j <= 2 * n && evt[j].first <= i) {
      int id = evt[j++].second;
      if (!on[id]) {
        seg[(i & 1) ^ 1].upd(1, i - 1, 1);
        seg[(i & 1) ^ 1].upd((i & 1) ^ 1, pos[id].first, pos[id].second, 1);
        seg[i & 1].upd(i & 1, pos[id].first, pos[id].second, 1);
      } else {
        int sta = pos[id].first;
        if ((pos[id].second - pos[id].first + 1) & 1) {
          seg[(sta & 1) ^ 1].upd(1, sta - 1, -1);
          seg[(sta & 1) ^ 1].upd((sta & 1) ^ 1, pos[id].first, pos[id].second,
                                 -1);
          seg[(sta & 1) ^ 1].upd(sta & 1, pos[id].first, pos[id].second, 1);
        } else {
          seg[sta & 1].upd(sta & 1, pos[id].first, pos[id].second, -1);
          seg[sta & 1].upd(1, sta - 1, 1);
          seg[sta & 1].upd((sta & 1) ^ 1, pos[id].first, pos[id].second, 1);
        }
      }
      on[id] ^= 1;
    }
    pair<long long, long long> res = seg[i & 1].qu(1, i);
    ans += 1LL * (i + 1) * res.second - res.first;
  }
  printf("%lld\n", ans);
  return 0;
}

### Prompt

In cpp, your task is to solve the following problem:

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 GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("no-stack-protector")
#pragma GCC target("sse,sse2,ssse3,sse3,sse4,popcnt,avx,mmx,abm,tune=native")
using namespace std;
namespace output {
void __(short x) { cout << x; }
void __(unsigned x) { cout << x; }
void __(int x) { cout << x; }
void __(long long x) { cout << x; }
void __(unsigned long long x) { cout << x; }
void __(double x) { cout << x; }
void __(long double x) { cout << x; }
void __(char x) { cout << x; }
void __(const char* x) { cout << x; }
void __(const string& x) { cout << x; }
void __(bool x) { cout << (x ? "true" : "false"); }
template <class S, class T>
void __(const pair<S, T>& x) {
  __(1 ? "(" : ""), __(x.first), __(1 ? ", " : " "), __(x.second),
      __(1 ? ")" : "");
}
template <class T>
void __(const vector<T>& x) {
  __(1 ? "{" : "");
  bool _ = 0;
  for (const auto& v : x) __(_ ? 1 ? ", " : " " : ""), __(v), _ = 1;
  __(1 ? "}" : "");
}
template <class T>
void __(const set<T>& x) {
  __(1 ? "{" : "");
  bool _ = 0;
  for (const auto& v : x) __(_ ? 1 ? ", " : " " : ""), __(v), _ = 1;
  __(1 ? "}" : "");
}
template <class T>
void __(const multiset<T>& x) {
  __(1 ? "{" : "");
  bool _ = 0;
  for (const auto& v : x) __(_ ? 1 ? ", " : " " : ""), __(v), _ = 1;
  __(1 ? "}" : "");
}
template <class S, class T>
void __(const map<S, T>& x) {
  __(1 ? "{" : "");
  bool _ = 0;
  for (const auto& v : x) __(_ ? 1 ? ", " : " " : ""), __(v), _ = 1;
  __(1 ? "}" : "");
}
void pr() { cout << "\n"; }
template <class S, class... T>
void pr(const S& a, const T&... b) {
  __(a);
  if (sizeof...(b)) __(' ');
  pr(b...);
}
}  // namespace output
using namespace output;
const int MN = 2e5 + 5;
int n, m, i, j, x, y, on[MN], mrk[MN];
pair<int, int> evt[2 * MN], pos[MN];
long long sm[2], ans;
struct dblseg {
  struct idk {
    long long mn, sm, cnt;
  };
  struct nd {
    idk a;
    long long lz;
  } st[2][2 * MN];
  long long n, m;
  void build(int id, int i, int s, int e) {
    if (s < e) {
      build(id, 2 * i, s, (s + e) / 2);
      build(id, 2 * i + 1, (s + e) / 2 + 1, e);
      st[id][i].lz = st[id][i].a.mn = 0;
      st[id][i].a.sm = st[id][2 * i].a.sm + st[id][2 * i + 1].a.sm;
      st[id][i].a.cnt = st[id][2 * i].a.cnt + st[id][2 * i + 1].a.cnt;
    } else if (s == e) {
      st[id][i].a.mn = st[id][i].lz = 0;
      st[id][i].a.sm = 2 * s - 1 + id;
      st[id][i].a.cnt = 1;
    }
  }
  void init(int sz) {
    n = ceil(sz / 2.0);
    m = sz / 2;
    build(0, 1, 1, n);
    build(1, 1, 1, m);
  }
  inline void upd_lz(int id, int i, int s, int e) {
    if (st[id][i].lz) {
      st[id][i].a.mn += st[id][i].lz;
      if (s != e) {
        st[id][2 * i].lz += st[id][i].lz;
        st[id][2 * i + 1].lz += st[id][i].lz;
      }
      st[id][i].lz = 0;
    }
  }
  void upd(int id, int i, int s, int e, int ss, int se, int val) {
    if (ss > se) return;
    upd_lz(id, i, s, e);
    if (s >= ss && e <= se) {
      st[id][i].lz = val;
      upd_lz(id, i, s, e);
    } else {
      if ((s + e) / 2 < ss)
        upd(id, 2 * i + 1, (s + e) / 2 + 1, e, ss, se, val),
            upd_lz(id, 2 * i, s, (s + e) / 2);
      else if ((s + e) / 2 >= se)
        upd(id, 2 * i, s, (s + e) / 2, ss, se, val),
            upd_lz(id, 2 * i + 1, (s + e) / 2 + 1, e);
      else
        upd(id, 2 * i, s, (s + e) / 2, ss, se, val),
            upd(id, 2 * i + 1, (s + e) / 2 + 1, e, ss, se, val);
      st[id][i].a.mn = min(st[id][2 * i].a.mn, st[id][2 * i + 1].a.mn);
      st[id][i].a.sm =
          (st[id][2 * i].a.mn == st[id][i].a.mn ? st[id][2 * i].a.sm : 0) +
          (st[id][2 * i + 1].a.mn == st[id][i].a.mn ? st[id][2 * i + 1].a.sm
                                                    : 0);
      st[id][i].a.cnt =
          (st[id][2 * i].a.mn == st[id][i].a.mn ? st[id][2 * i].a.cnt : 0) +
          (st[id][2 * i + 1].a.mn == st[id][i].a.mn ? st[id][2 * i + 1].a.cnt
                                                    : 0);
    }
  }
  idk qu(int id, int i, int s, int e, int ss, int se) {
    if (ss > se) return {1 << 30, 0, 0};
    upd_lz(id, i, s, e);
    if (s >= ss && e <= se)
      return st[id][i].a;
    else if ((s + e) / 2 < ss)
      return qu(id, 2 * i + 1, (s + e) / 2 + 1, e, ss, se);
    else if ((s + e) / 2 >= se)
      return qu(id, 2 * i, s, (s + e) / 2, ss, se);
    else {
      idk l = qu(id, 2 * i, s, (s + e) / 2, ss, se),
          r = qu(id, 2 * i + 1, (s + e) / 2 + 1, e, ss, se);
      long long mn = min(l.mn, r.mn);
      return {mn, (l.mn == mn ? l.sm : 0) + (r.mn == mn ? r.sm : 0),
              (l.mn == mn ? l.cnt : 0) + (r.mn == mn ? r.cnt : 0)};
    }
  }
  inline void upd(int id, int s, int e, int delta) {
    if (((s + 1) & 1) != id) s++;
    if (((e + 1) & 1) != id) e--;
    if (s > e) return;
    int l = (s - 1) / 2 + 1, r = (e - 1) / 2 + 1;
    upd(id, 1, 1, id ? m : n, l, r, delta);
  }
  inline void upd(int s, int e, int delta) {
    upd(0, s, e, delta);
    upd(1, s, e, delta);
  }
  inline pair<long long, long long> qu(int s, int e) {
    idk a[2];
    for (int i = 0; i < 2; i++) {
      int l = s, r = e;
      if (((l + 1) & 1) != i) l++;
      if (((r + 1) & 1) != i) r--;
      if (l > r) {
        a[i] = {1 << 30, 0, 0};
        continue;
      }
      l = (l - 1) / 2 + 1, r = (r - 1) / 2 + 1;
      a[i] = qu(i, 1, 1, i ? m : n, l, r);
    }
    return make_pair((!a[0].mn ? a[0].sm : 0) + (!a[1].mn ? a[1].sm : 0),
                     (!a[0].mn ? a[0].cnt : 0) + (!a[1].mn ? a[1].cnt : 0));
  }
} seg[2];
int main() {
  for (scanf("%d%d", &n, &m), i = 1; i <= n; i++) {
    scanf("%d%d", &x, &y);
    evt[2 * i - 1] = {x, i};
    evt[2 * i] = {y + 1, i};
    pos[i] = {x, y};
    mrk[x]++;
    mrk[y + 1]--;
  }
  int cnt = 0;
  for (i = 1; i <= m; i++) {
    mrk[i] += mrk[i - 1];
    if (!mrk[i])
      cnt++;
    else
      cnt = 0;
    ans -= 1LL * cnt * (cnt + 1) / 2;
  }
  seg[0].init(m);
  seg[1].init(m);
  sort(evt + 1, evt + 2 * n + 1,
       [](pair<int, int> i, pair<int, int> j) { return i.first < j.first; });
  for (i = j = 1; i <= m; i++) {
    while (j <= 2 * n && evt[j].first <= i) {
      int id = evt[j++].second;
      if (!on[id]) {
        seg[(i & 1) ^ 1].upd(1, i - 1, 1);
        seg[(i & 1) ^ 1].upd((i & 1) ^ 1, pos[id].first, pos[id].second, 1);
        seg[i & 1].upd(i & 1, pos[id].first, pos[id].second, 1);
      } else {
        int sta = pos[id].first;
        if ((pos[id].second - pos[id].first + 1) & 1) {
          seg[(sta & 1) ^ 1].upd(1, sta - 1, -1);
          seg[(sta & 1) ^ 1].upd((sta & 1) ^ 1, pos[id].first, pos[id].second,
                                 -1);
          seg[(sta & 1) ^ 1].upd(sta & 1, pos[id].first, pos[id].second, 1);
        } else {
          seg[sta & 1].upd(sta & 1, pos[id].first, pos[id].second, -1);
          seg[sta & 1].upd(1, sta - 1, 1);
          seg[sta & 1].upd((sta & 1) ^ 1, pos[id].first, pos[id].second, 1);
        }
      }
      on[id] ^= 1;
    }
    pair<long long, long long> res = seg[i & 1].qu(1, i);
    ans += 1LL * (i + 1) * res.second - res.first;
  }
  printf("%lld\n", ans);
  return 0;
}

```