799_F. Beautiful fountains rows_10328
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).
#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;
};
pair<int, int> get_parity_segment(pair<int, int> q, int par) {
  if ((q.first + par) & 1) {
    ++q.first;
  }
  if ((q.second + par) & 1) {
    --q.second;
  }
  return {q.first >> 1, q.second >> 1};
};
const int shift = 1 << 18;
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;
}

1 5
2 4
 3 6
2 4
3 6
4 4
 30 1000
108 129
314 314
392 421
971 971
561 565
307 310
993 999
957 979
938 944
32 60
809 835
45 58
467 476
237 265
887 899
889 909
528 554
715 736
380 402
947 968
91 100
512 541
115 117
874 898
622 638
34 34
747 771
37 49
945 950
311 332
 3 10
7 10
6 10
2 8
 30 1000
281 297
568 568
173 177
34 46
164 170
289 301
931 933
703 705
366 368
252 258
270 292
616 616
306 306
605 629
69 91
904 916
732 750
292 320
771 785
317 333
450 458
250 264
310 330
54 62
85 87
694 700
947 949
328 354
823 851
873 895
 30 1000
592 595
956 979
814 839
342 347
86 105
340 357
38 39
328 339
364 367
759 766
36 45
11 36
880 903
808 829
676 705
541 542
298 315
258 283
292 315
753 754
487 496
327 344
825 852
617 636
326 345
708 719
223 252
382 401
69 82
15 44
 10 3
1 2
3 3
1 2
1 1
2 2
1 3
1 2
1 1
2 3
1 3
 30 1000
17 189
337 881
343 505
452 874
215 443
103 819
11 993
253 323
22 858
155 797
34 84
321 865
303 983
122 132
167 765
9 981
66 962
106 706
165 935
68 732
501 543
517 543
301 409
460 626
135 987
22 972
297 373
15 893
100 954
307 625
 30 1000
627 985
130 336
2 999
524 986
253 513
181 534
52 962
295 856
108 613
288 907
217 984
417 593
520 1000
46 303
416 701
23 885
15 878
156 775
166 728
154 577
80 805
29 985
15 945
100 869
576 728
680 716
596 906
163 665
597 719
197 843
 1 200000
32092 64910
 30 1000
340 839
435 672
187 586
114 947
110 469
234 549
18 839
337 858
154 755
263 292
523 804
325 610
68 399
666 747
40 689
39 1000
187 934
256 577
353 678
134 847
168 663
84 889
657 658
19 972
1 964
749 888
271 754
54 959
69 930
2 999
 10 10
6 6
4 6
1 6
3 10
3 9
4 8
7 9
5 5
6 10
1 6
 30 1000
108 129
314 314
392 421
971 971
561 565
234 310
993 999
957 979
938 944
32 60
809 835
45 58
467 476
237 265
887 899
889 909
528 554
715 736
380 402
947 968
91 100
512 541
115 117
874 898
622 638
34 34
747 771
37 49
945 950
311 332
 3 10
2 10
6 10
2 8
 30 1000
17 189
337 881
343 505
809 874
215 443
103 819
11 993
253 323
22 858
155 797
34 84
321 865
303 983
122 132
167 765
9 981
66 962
106 706
165 935
68 732
501 543
517 543
301 409
460 626
135 987
22 972
297 373
15 893
100 954
307 625
 1 200000
32092 110777
 30 1000
340 839
435 672
187 586
114 947
110 469
234 549
18 682
337 858
154 755
263 292
523 804
325 610
68 399
666 747
40 689
39 1000
187 934
256 577
353 678
134 847
168 663
84 889
657 658
19 972
1 964
749 888
271 754
54 959
69 930
2 999
 10 10
6 6
4 6
1 6
3 10
3 9
4 8
7 9
5 5
10 10
1 6
 30 1000
108 129
314 314
392 421
971 971
561 565
234 310
993 999
957 979
938 944
32 60
809 835
27 58
467 476
237 265
887 899
889 909
528 554
715 736
380 402
947 968
91 100
512 541
115 117
874 898
622 638
34 34
747 771
37 49
945 950
311 332
 30 1000
17 189
337 881
343 505
809 874
215 443
103 819
11 993
253 323
22 858
155 797
34 84
321 327
303 983
122 132
167 765
9 981
66 962
106 706
165 935
68 732
501 543
517 543
301 409
460 626
135 987
22 972
297 373
15 893
100 954
307 625
 30 1000
340 839
435 672
187 586
114 947
110 469
234 549
18 682
337 858
154 755
263 292
523 804
325 610
68 399
666 747
40 689
39 1000
187 303
256 577
353 678
134 847
168 663
84 889
657 658
19 972
1 964
749 888
271 754
54 959
69 930
2 999
 10 10
6 6
4 6
1 6
3 10
3 9
4 7
7 9
5 5
10 10
1 6
 30 1000
17 189
337 881
343 505
809 874
215 443
103 819
11 993
253 323
22 858
155 797
34 84
321 327
303 983
122 132
167 765
9 981
66 66
106 706
165 935
68 732
501 543
517 543
301 409
460 626
135 987
22 972
297 373
15 893
100 954
307 625
 30 1000
340 839
435 672
366 586
114 947
110 469
234 549
18 682
337 858
154 755
263 292
523 804
325 610
68 399
666 747
40 689
39 1000
187 303
256 577
353 678
134 847
168 663
84 889
657 658
19 972
1 964
749 888
271 754
54 959
69 930
2 999
 30 1000
17 189
337 881
343 505
809 874
215 443
103 819
11 993
253 323
22 858
155 797
34 84
321 327
303 983
122 132
167 765
9 981
66 66
106 706
165 935
68 732
501 543
517 543
301 409
460 626
135 987
22 972
297 373
15 893
100 954
307 535
 30 1000
17 189
337 881
343 505
809 874
215 443
103 819
11 993
253 323
22 858
155 797
34 84
321 327
303 983
122 132
167 765
9 981
66 66
106 706
165 935
68 732
501 543
289 543
301 409
460 626
135 987
22 972
297 373
15 893
100 954
307 535
 30 1000
17 189
337 881
343 505
809 874
215 443
103 819
11 993
253 323
22 858
155 797
34 84
321 327
303 983
122 132
167 765
9 981
66 66
106 706
165 935
111 732
501 543
289 543
301 409
460 626
135 987
22 972
297 373
15 893
100 954
307 535
 30 1000
592 595
956 979
814 839
342 347
86 105
340 357
38 39
132 339
364 367
759 766
36 45
11 36
880 903
808 829
676 705
541 542
298 315
258 283
292 315
753 754
487 496
327 344
825 852
617 636
326 345
708 719
223 252
382 401
69 82
15 44
 30 1000
17 189
337 881
343 505
452 874
215 443
103 819
11 993
253 323
22 858
155 797
34 84
321 865
303 983
122 132
167 765
9 981
66 962
106 706
165 935
68 732
501 543
517 959
301 409
460 626
135 987
22 972
297 373
15 893
100 954
307 625
 1 200000
32645 64910
 30 1000
108 129
314 314
392 421
971 971
561 565
234 310
993 999
957 979
938 944
32 60
809 835
45 58
467 476
237 265
887 899
889 909
528 554
715 736
380 402
625 968
91 100
512 541
115 117
874 898
622 638
34 34
747 771
37 49
945 950
311 332
 30 1000
340 839
435 672
187 586
114 947
110 469
234 549
18 682
11 858
154 755
263 292
523 804
325 610
68 399
666 747
40 689
39 1000
187 934
256 577
353 678
134 847
168 663
84 889
657 658
19 972
1 964
749 888
271 754
54 959
69 930
2 999
 30 1000
17 189
337 881
343 505
809 874
215 443
103 819
11 993
253 323
22 858
155 797
34 84
321 327
303 983
122 132
167 765
9 981
66 962
106 706
165 935
68 732
501 543
517 543
301 409
157 626
135 987
22 972
297 373
15 893
100 954
307 625
 30 1000
340 839
435 672
187 586
114 947
110 469
234 549
18 682
337 858
154 755
263 292
523 804
325 610
68 399
666 747
40 689
39 1000
187 303
256 577
353 678
134 847
168 663
84 889
657 658
19 972
1 964
661 888
271 754
54 959
69 930
2 999
 30 1000
5 189
337 881
343 505
809 874
215 443
103 819
11 993
253 323
22 858
155 797
34 84
321 327
303 983
122 132
167 765
9 981
66 66
106 706
165 935
68 732
501 543
517 543
301 409
460 626
135 987
22 972
297 373
15 893
100 954
307 625
 30 1000
340 839
435 672
366 586
114 947
110 469
234 549
18 682
337 858
154 755
263 292
523 804
325 610
68 399
666 747
40 689
39 1000
187 303
256 577
353 678
90 847
168 663
84 889
657 658
19 972
1 964
749 888
271 754
54 959
69 930
2 999
 30 1000
17 189
337 881
12 505
809 874
215 443
103 819
11 993
253 323
22 858
155 797
34 84
321 327
303 983
122 132
167 765
9 981
66 66
106 706
165 935
68 732
501 543
517 543
301 409
460 626
135 987
22 972
297 373
15 893
100 954
307 535
 30 1000
17 189
337 881
343 505
809 874
215 443
103 819
11 993
253 323
22 858
155 797
34 84
321 327
303 983
122 132
167 765
9 981
66 66
106 706
165 935
111 732
271 543
289 543
301 409
460 626
135 987
22 972
297 373
15 893
100 954
307 535
 30 1000
592 595
956 979
814 839
342 347
86 105
340 357
38 39
132 339
364 367
759 766
36 45
11 36
880 903
808 829
676 705
541 542
298 315
258 283
292 315
753 754
487 496
327 344
825 852
617 636
326 345
708 719
223 252
382 401
69 82
15 30
 30 1000
17 189
337 881
343 505
452 874
215 443
103 526
11 993
253 323
22 858
155 797
34 84
321 865
303 983
122 132
167 765
9 981
66 962
106 706
165 935
68 732
501 543
517 959
301 409
460 626
135 987
22 972
297 373
15 893
100 954
307 625
 30 1000
108 129
314 314
392 421
971 971
561 565
234 310
993 999
957 979
938 944
32 60
809 835
45 58
467 476
237 265
887 899
889 909
528 554
715 736
380 402
625 968
91 100
512 541
115 117
874 898
622 638
34 34
747 771
37 49
945 950
73 332
 30 1000
340 839
435 672
187 586
114 947
110 469
234 549
18 682
11 858
154 755
263 521
523 804
325 610
68 399
666 747
40 689
39 1000
187 934
256 577
353 678
134 847
168 663
84 889
657 658
19 972
1 964
749 888
271 754
54 959
69 930
2 999
 30 1000
17 189
337 881
343 505
809 874
215 443
103 819
11 993
253 323
22 858
155 797
34 84
321 327
303 983
122 132
167 765
9 981
66 962
106 706
165 935
68 732
501 543
517 543
301 409
157 626
135 987
22 972
297 373
15 155
100 954
307 625
 30 1000
340 839
435 672
366 586
114 947
110 469
234 549
18 682
337 858
154 755
263 292
523 804
325 610
68 399
666 747
40 689
61 1000
187 303
256 577
353 678
90 847
168 663
84 889
657 658
19 972
1 964
749 888
271 754
54 959
69 930
2 999
 30 1000
17 286
337 881
343 505
452 874
215 443
103 526
11 993
253 323
22 858
155 797
34 84
321 865
303 983
122 132
167 765
9 981
66 962
106 706
165 935
68 732
501 543
517 959
301 409
460 626
135 987
22 972
297 373
15 893
100 954
307 625
 30 1000
108 129
314 314
392 421
971 971
561 565
234 310
993 999
957 979
938 944
32 60
809 835
45 58
467 476
237 265
887 899
889 909
528 554
715 736
380 402
625 968
91 100
512 541
115 198
874 898
622 638
34 34
747 771
37 49
945 950
73 332
 30 1000
17 189
337 881
343 505
809 874
215 443
103 819
11 993
253 323
22 858
155 797
34 84
321 327
303 983
122 132
167 765
9 981
66 962
106 706
165 935
68 732
501 543
517 543
301 409
157 626
135 987
22 972
297 373
15 155
100 954
422 625
 30 1000
17 189
337 881
343 505
809 874
215 443
103 819
11 993
253 323
22 858
155 797
34 84
321 327
303 983
122 132
167 765
9 981
66 962
106 706
165 935
68 732
501 543
517 543
301 409
159 626
135 987
22 972
297 373
15 155
100 954
422 625
 30 1000
17 189
337 881
343 505
809 874
215 443
103 819
11 993
253 323
22 858
155 797
34 84
321 327
303 983
122 132
167 765
9 981
66 962
106 706
165 935
68 732
501 543
517 543
301 409
159 626
135 987
22 972
297 373
15 155
100 954
622 625
 3 10
7 10
4 10
2 8
 30 1000
17 189
337 881
343 505
452 874
215 443
103 819
11 993
253 323
22 858
155 797
34 84
321 865
303 983
122 132
167 832
9 981
66 962
106 706
165 935
68 732
501 543
517 543
301 409
460 626
135 987
22 972
297 373
15 893
100 954
307 625
 30 1000
627 985
130 336
2 999
524 986
253 513
181 534
52 962
295 856
101 613
288 907
217 984
417 593
520 1000
46 303
416 701
23 885
15 878
156 775
166 728
154 577
80 805
29 985
15 945
100 869
576 728
680 716
596 906
163 665
597 719
197 843
 30 1000
340 839
435 672
187 586
114 947
110 469
234 549
18 839
337 858
154 755
263 292
646 804
325 610
68 399
666 747
40 689
39 1000
187 934
256 577
353 678
134 847
168 663
84 889
657 658
19 972
1 964
749 888
271 754
54 959
69 930
2 999
 1 9
2 4

23
 19
 2993968
 38
 116756195
 516246
 3
 2441952
 557289
 710812262846275
 882132
 16
 2802658
 92
 4894579
 405239161045020
 879324
 24
 2811284
 4900387
 874936
 19
 4900875
 735992
 5221811
 5221019
 5226859
 496582
 2438784
 202261644659789
 1922226
 879844
 5926876
 874943
 4902730
 737672
 5222046
 5227176
 497230
 2010667
 2621675
 897692
 5930404
 739388
 815307
 2484716
 1927248
 1927236
 5800836
 38
 2233180
 482105
 893823
 97
