#include <bits/stdc++.h>
using namespace std;
void err() { cout << endl; }
template <class T, class... Ts>
void err(T arg, Ts... args) {
  cout << arg << ' ';
  err(args...);
}
void read() {}
template <class T, class... Ts>
void read(T &x, Ts &...xs) {
  T f = 1;
  char ch;
  x = 0;
  for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) {
    if (ch == '-') f = -1;
  }
  for (; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
  x *= f;
  read(xs...);
}
template <class T>
void myHash(T a[], int n, T w[] = nullptr) {
  set<T> st;
  for (int i = 0; i < n; i++) {
    st.insert(a[i]);
  }
  int tot = 0;
  map<T, int> mp;
  for (T x : st) {
    mp[x] = ++tot;
  }
  for (int i = 0; i < n; i++) {
    a[i] = mp[a[i]];
  }
  if (w != nullptr) {
    for (pair<T, int> p : mp) {
      w[p.second] = p.first;
    }
  }
}
const int maxn = 2e5 + 7;
const int inf = 0x3f3f3f3f;
const long long INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
int up(int x) { return (int)ceil(x / 2.0); }
struct Tag {
  bool clr;
  void mergeTag(Tag k) { clr |= k.clr; }
  void clear() { clr = false; }
};
struct Info {
  long long sum, cnt;
  void applyTag(Tag k) {
    if (k.clr) {
      sum = 0;
      cnt = 0;
    }
  }
};
struct SegTree {
  Info info[maxn << 2];
  Tag tag[maxn << 2];
  int n, w[maxn], p;
  void init(int _n, int _w[], int _p) {
    n = _n;
    p = _p;
    for (int i = 1; i <= n; i++) {
      w[i] = _w[i];
    }
    build(1, 1, n);
  }
  Info mergeInfo(Info x, Info y) { return {x.sum + y.sum, x.cnt + y.cnt}; }
  void applyTag(int x, Tag k) {
    info[x].applyTag(k);
    tag[x].mergeTag(k);
  }
  void pushup(int x) { info[x] = mergeInfo(info[x * 2], info[x * 2 + 1]); }
  void pushdown(int x) {
    applyTag(x * 2, tag[x]);
    applyTag(x * 2 + 1, tag[x]);
    tag[x].clear();
  }
  void build(int x, int l, int r) {
    tag[x].clear();
    if (l == r) {
      info[x] = {w[l], 1};
    } else {
      int mid = l + r >> 1;
      build(x * 2, l, mid);
      build(x * 2 + 1, mid + 1, r);
      pushup(x);
    }
  }
  void update(int x, int l, int r, int ql, int qr) {
    if (r < ql || l > qr) return;
    if (ql <= l && r <= qr) {
      applyTag(x, {true});
      return;
    }
    pushdown(x);
    int mid = l + r >> 1;
    update(x * 2, l, mid, ql, qr);
    update(x * 2 + 1, mid + 1, r, ql, qr);
    pushup(x);
  }
  Info query(int x, int l, int r, int ql, int qr) {
    if (r < ql || l > qr) return {0};
    if (ql <= l && r <= qr) {
      return info[x];
    }
    pushdown(x);
    int mid = l + r >> 1;
    return mergeInfo(query(x * 2, l, mid, ql, qr),
                     query(x * 2 + 1, mid + 1, r, ql, qr));
  }
  void change(int l, int r) {
    if ((l & 1) != p) l++;
    if ((r & 1) != p) r--;
    if (l > r) return;
    update(1, 1, n, up(l), up(r));
  }
  long long ask(int l, int r, int a) {
    if ((l & 1) != p) l++;
    if ((r & 1) != p) r--;
    if (l > r) return 0;
    Info ans = query(1, 1, n, up(l), up(r));
    return ans.sum - 1ll * ans.cnt * (a - 1);
  }
} t[2];
vector<int> vx[maxn], vy[maxn];
int x[maxn], y[maxn];
int w[2][maxn];
int dif[maxn], sd[maxn];
int fs[maxn];
void run() {
  int n, m;
  read(n, m);
  for (int i = 1; i <= n; i++) {
    read(x[i], y[i]);
    vx[x[i]].push_back(i);
    vy[y[i]].push_back(i);
    dif[x[i]]++;
    dif[y[i] + 1]--;
  }
  for (int i = 1; i <= m; i++) {
    sd[i] = sd[i - 1] + dif[i];
  }
  fs[m + 1] = m + 1;
  for (int i = m; i >= 1; i--) {
    if (sd[i]) {
      fs[i] = i;
    } else {
      fs[i] = fs[i + 1];
    }
  }
  for (int i = 1; i <= m; i++) {
    w[i & 1][up(i)] = i;
  }
  if (m > 1) t[0].init(m / 2, w[0], 0);
  t[1].init(up(m), w[1], 1);
  set<pair<int, int> > R[2];
  long long ans = 0;
  for (int a = m; a >= 1; a--) {
    int c = a & 1;
    int rc = c ^ 1;
    for (int i : vy[a]) {
      R[c].insert({a, i});
    }
    for (int i : vx[a]) {
      R[y[i] & 1].erase({y[i], i});
      t[rc].change(x[i] + 1, y[i]);
      if ((y[i] - x[i]) & 1) {
        t[y[i] & 1].change(y[i], m);
        t[(y[i] + 1) & 1].change(y[i] + 1, m);
      }
    }
    if (R[rc].empty()) {
      ans += t[c].ask(fs[a], m, a);
    } else {
      int b = R[rc].begin()->first;
      ans += t[c].ask(fs[a], b, a);
    }
    if (!R[rc].empty()) continue;
    if (R[c].empty()) {
      ans += t[rc].ask(max(a + 1, fs[a]), m, a);
    } else {
      int b = R[c].rbegin()->first;
      ans += t[rc].ask(max(b + 1, fs[a]), m, a);
    }
  }
  printf("%lld\n", ans);
}
int main() {
  int T = 1;
  while (T--) {
    run();
  }
  return 0;
}

### 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>
using namespace std;
void err() { cout << endl; }
template <class T, class... Ts>
void err(T arg, Ts... args) {
  cout << arg << ' ';
  err(args...);
}
void read() {}
template <class T, class... Ts>
void read(T &x, Ts &...xs) {
  T f = 1;
  char ch;
  x = 0;
  for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) {
    if (ch == '-') f = -1;
  }
  for (; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
  x *= f;
  read(xs...);
}
template <class T>
void myHash(T a[], int n, T w[] = nullptr) {
  set<T> st;
  for (int i = 0; i < n; i++) {
    st.insert(a[i]);
  }
  int tot = 0;
  map<T, int> mp;
  for (T x : st) {
    mp[x] = ++tot;
  }
  for (int i = 0; i < n; i++) {
    a[i] = mp[a[i]];
  }
  if (w != nullptr) {
    for (pair<T, int> p : mp) {
      w[p.second] = p.first;
    }
  }
}
const int maxn = 2e5 + 7;
const int inf = 0x3f3f3f3f;
const long long INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
int up(int x) { return (int)ceil(x / 2.0); }
struct Tag {
  bool clr;
  void mergeTag(Tag k) { clr |= k.clr; }
  void clear() { clr = false; }
};
struct Info {
  long long sum, cnt;
  void applyTag(Tag k) {
    if (k.clr) {
      sum = 0;
      cnt = 0;
    }
  }
};
struct SegTree {
  Info info[maxn << 2];
  Tag tag[maxn << 2];
  int n, w[maxn], p;
  void init(int _n, int _w[], int _p) {
    n = _n;
    p = _p;
    for (int i = 1; i <= n; i++) {
      w[i] = _w[i];
    }
    build(1, 1, n);
  }
  Info mergeInfo(Info x, Info y) { return {x.sum + y.sum, x.cnt + y.cnt}; }
  void applyTag(int x, Tag k) {
    info[x].applyTag(k);
    tag[x].mergeTag(k);
  }
  void pushup(int x) { info[x] = mergeInfo(info[x * 2], info[x * 2 + 1]); }
  void pushdown(int x) {
    applyTag(x * 2, tag[x]);
    applyTag(x * 2 + 1, tag[x]);
    tag[x].clear();
  }
  void build(int x, int l, int r) {
    tag[x].clear();
    if (l == r) {
      info[x] = {w[l], 1};
    } else {
      int mid = l + r >> 1;
      build(x * 2, l, mid);
      build(x * 2 + 1, mid + 1, r);
      pushup(x);
    }
  }
  void update(int x, int l, int r, int ql, int qr) {
    if (r < ql || l > qr) return;
    if (ql <= l && r <= qr) {
      applyTag(x, {true});
      return;
    }
    pushdown(x);
    int mid = l + r >> 1;
    update(x * 2, l, mid, ql, qr);
    update(x * 2 + 1, mid + 1, r, ql, qr);
    pushup(x);
  }
  Info query(int x, int l, int r, int ql, int qr) {
    if (r < ql || l > qr) return {0};
    if (ql <= l && r <= qr) {
      return info[x];
    }
    pushdown(x);
    int mid = l + r >> 1;
    return mergeInfo(query(x * 2, l, mid, ql, qr),
                     query(x * 2 + 1, mid + 1, r, ql, qr));
  }
  void change(int l, int r) {
    if ((l & 1) != p) l++;
    if ((r & 1) != p) r--;
    if (l > r) return;
    update(1, 1, n, up(l), up(r));
  }
  long long ask(int l, int r, int a) {
    if ((l & 1) != p) l++;
    if ((r & 1) != p) r--;
    if (l > r) return 0;
    Info ans = query(1, 1, n, up(l), up(r));
    return ans.sum - 1ll * ans.cnt * (a - 1);
  }
} t[2];
vector<int> vx[maxn], vy[maxn];
int x[maxn], y[maxn];
int w[2][maxn];
int dif[maxn], sd[maxn];
int fs[maxn];
void run() {
  int n, m;
  read(n, m);
  for (int i = 1; i <= n; i++) {
    read(x[i], y[i]);
    vx[x[i]].push_back(i);
    vy[y[i]].push_back(i);
    dif[x[i]]++;
    dif[y[i] + 1]--;
  }
  for (int i = 1; i <= m; i++) {
    sd[i] = sd[i - 1] + dif[i];
  }
  fs[m + 1] = m + 1;
  for (int i = m; i >= 1; i--) {
    if (sd[i]) {
      fs[i] = i;
    } else {
      fs[i] = fs[i + 1];
    }
  }
  for (int i = 1; i <= m; i++) {
    w[i & 1][up(i)] = i;
  }
  if (m > 1) t[0].init(m / 2, w[0], 0);
  t[1].init(up(m), w[1], 1);
  set<pair<int, int> > R[2];
  long long ans = 0;
  for (int a = m; a >= 1; a--) {
    int c = a & 1;
    int rc = c ^ 1;
    for (int i : vy[a]) {
      R[c].insert({a, i});
    }
    for (int i : vx[a]) {
      R[y[i] & 1].erase({y[i], i});
      t[rc].change(x[i] + 1, y[i]);
      if ((y[i] - x[i]) & 1) {
        t[y[i] & 1].change(y[i], m);
        t[(y[i] + 1) & 1].change(y[i] + 1, m);
      }
    }
    if (R[rc].empty()) {
      ans += t[c].ask(fs[a], m, a);
    } else {
      int b = R[rc].begin()->first;
      ans += t[c].ask(fs[a], b, a);
    }
    if (!R[rc].empty()) continue;
    if (R[c].empty()) {
      ans += t[rc].ask(max(a + 1, fs[a]), m, a);
    } else {
      int b = R[c].rbegin()->first;
      ans += t[rc].ask(max(b + 1, fs[a]), m, a);
    }
  }
  printf("%lld\n", ans);
}
int main() {
  int T = 1;
  while (T--) {
    run();
  }
  return 0;
}

```