#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val) {
  std::fill((T *)array, (T *)(array + N), val);
}
struct Edge {
  int from, to, weight;
};
template <class T, class OP, class PROP>
class Lazy_Segment_Tree {
 public:
  vector<T> data, lazy;
  vector<bool> isupd;
  int n;
  Lazy_Segment_Tree(int a) : n(1) {
    while (n < a) n *= 2;
    data.resize(n * 2 - 1);
    lazy.resize(n * 2 - 1);
    isupd.resize(n * 2 - 1);
  }
  void prop(int num, int s) {
    if (isupd[num]) {
      data[num] = PROP()(data[num], lazy[num], 1, s);
      if (num < n - 1) {
        lazy[num * 2 + 1] = PROP()(lazy[num * 2 + 1], lazy[num]);
        lazy[num * 2 + 2] = PROP()(lazy[num * 2 + 2], lazy[num]);
        isupd[num * 2 + 1] = 1;
        isupd[num * 2 + 2] = 1;
      }
      lazy[num] = T();
      isupd[num] = 0;
    }
  }
  void op(int a, int b, T v, int num = 0, int base = 1) {
    int l = (num + 1 - base) * (n / base), r = l + n / base;
    prop(num, r - l);
    if (a == l && b == r) {
      isupd[num] = 1;
      lazy[num] = PROP()(lazy[num], v);
      prop(num, r - l);
    } else {
      int nr = (l + r) / 2;
      if (nr > a) op(a, min(b, nr), v, num * 2 + 1, base * 2);
      if (nr < b) op(max(a, nr), b, v, num * 2 + 2, base * 2);
      prop(num * 2 + 1, (r - l) / 2), prop(num * 2 + 2, (r - l) / 2);
      data[num] = OP()(data[num * 2 + 1], data[num * 2 + 2]);
    }
  }
  T query(int a, int b, int num = 0, int base = 1) {
    int l = (num + 1 - base) * (n / base), r = l + n / base;
    prop(num, r - l);
    if (a == l && b == r)
      return data[num];
    else {
      int nr = (l + r) / 2;
      T ret = T();
      if (nr > a) ret = OP()(ret, query(a, min(b, nr), num * 2 + 1, base * 2));
      if (nr < b) ret = OP()(ret, query(max(a, nr), b, num * 2 + 2, base * 2));
      return ret;
    }
  }
};
template <class T>
class ADD {
 public:
  T operator()(const T a, const T b, const int ra = 1, int rb = 1) {
    return a * ra + b * rb;
  }
};
template <class T>
class UPD {
 public:
  T operator()(const T a, const T b, const int ra = 1, int rb = 1) { return b; }
};
template <class T>
class RMQ {
 public:
  T operator()(const T a, const T b) { return min(a, b); }
};
template <class T>
class SUM {
 public:
  T operator()(const T a, const T b) { return a + b; }
};
struct N {
 public:
  long long num;
  N(long long num) : num(num) {}
  N() : num(0) {}
  N operator+(const N obj) const { return N(obj.num + num); }
  N operator*(const N obj) const { return N(obj.num * num); }
  bool operator<(const N obj) const { return obj.num > num; }
};
int main(void) {
  int n, m;
  cin >> n >> m;
  vector<vector<Edge>> g(n);
  for (int i = (0); (m) > i; i++) {
    int a, b;
    scanf("%d %d", &a, &b);
    a--, b--;
    g[a].push_back({a, b, 1});
    g[b].push_back({b, a, 1});
  }
  vector<pair<int, int>> circle;
  vector<int> visited(n, -1);
  int vn = 0;
  stack<int> st;
  function<void(int, int)> dfs = [&](int c, int p) {
    if (visited[c] != -1) {
      if (visited[c] < visited[p]) {
        stack<int> buf;
        int Min = INT_MAX, Max = INT_MIN;
        while (1) {
          int cur = st.top();
          buf.push(cur);
          st.pop();
          Min = min(Min, cur);
          Max = max(Max, cur);
          if (cur == c) break;
        }
        circle.push_back({Min, Max});
        while (buf.size()) st.push(buf.top()), buf.pop();
      }
      return;
    }
    visited[c] = vn;
    vn++;
    st.push(c);
    for (auto itr : g[c])
      if (itr.to != p) dfs(itr.to, c);
    st.pop();
  };
  for (int i = (0); (n) > i; i++) {
    if (visited[i] == -1) dfs(i, -1);
  }
  vector<int> kyo(n);
  set<pair<int, int>> cir;
  for (auto itr : circle) cir.insert({itr.second, itr.first});
  sort((circle).begin(), (circle).end());
  int cc = 0;
  for (int i = (0); (n) > i; i++) {
    if (cir.size() == 0) {
      kyo[i] = n;
    } else
      kyo[i] = cir.begin()->first;
    for (; circle.size() > cc; cc++) {
      if (circle[cc].first > i) break;
      cir.erase({circle[cc].second, circle[cc].first});
    }
  }
  vector<long long> rui(n + 1);
  for (int i = (0); (n) > i; i++) {
    rui[i + 1] = rui[i] + (kyo[i] - i);
  }
  int q;
  cin >> q;
  for (int i = (0); (q) > i; i++) {
    int l, r;
    scanf("%d %d", &l, &r);
    l--;
    int m = lower_bound(kyo.begin() + l, kyo.end(), r) - kyo.begin();
    long long ans = rui[min(r, m)] - rui[l];
    if (rui[min(r, m)] - rui[l] < 0) return 1;
    if (m < r) ans += ((r * 1LL - m) + 1) * (r - m) / 2;
    printf("%lld\n", ans);
  }
  return 0;
}

### Prompt

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

You are given an undirected graph with n vertices. There are no edge-simple cycles with the even length in it. In other words, there are no cycles of even length that pass each edge at most once. Let's enumerate vertices from 1 to n. 

You have to answer q queries. Each query is described by a segment of vertices [l; r], and you have to count the number of its subsegments [x; y] (l ≤ x ≤ y ≤ r), such that if we delete all vertices except the segment of vertices [x; y] (including x and y) and edges between them, the resulting graph is bipartite.

Input

The first line contains two integers n and m (1 ≤ n ≤ 3·105, 1 ≤ m ≤ 3·105) — the number of vertices and the number of edges in the graph.

The next m lines describe edges in the graph. The i-th of these lines contains two integers ai and bi (1 ≤ ai, bi ≤ n; ai ≠ bi), denoting an edge between vertices ai and bi. It is guaranteed that this graph does not contain edge-simple cycles of even length.

The next line contains a single integer q (1 ≤ q ≤ 3·105) — the number of queries.

The next q lines contain queries. The i-th of these lines contains two integers li and ri (1 ≤ li ≤ ri ≤ n) — the query parameters.

Output

Print q numbers, each in new line: the i-th of them should be the number of subsegments [x; y] (li ≤ x ≤ y ≤ ri), such that the graph that only includes vertices from segment [x; y] and edges between them is bipartite.

Examples

Input

6 6
1 2
2 3
3 1
4 5
5 6
6 4
3
1 3
4 6
1 6


Output

5
5
14


Input

8 9
1 2
2 3
3 1
4 5
5 6
6 7
7 8
8 4
7 2
3
1 8
1 4
3 8


Output

27
8
19

Note

The first example is shown on the picture below:

<image>

For the first query, all subsegments of [1; 3], except this segment itself, are suitable.

For the first query, all subsegments of [4; 6], except this segment itself, are suitable.

For the third query, all subsegments of [1; 6] are suitable, except [1; 3], [1; 4], [1; 5], [1; 6], [2; 6], [3; 6], [4; 6].

The second example is shown on the picture below:

<image>

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val) {
  std::fill((T *)array, (T *)(array + N), val);
}
struct Edge {
  int from, to, weight;
};
template <class T, class OP, class PROP>
class Lazy_Segment_Tree {
 public:
  vector<T> data, lazy;
  vector<bool> isupd;
  int n;
  Lazy_Segment_Tree(int a) : n(1) {
    while (n < a) n *= 2;
    data.resize(n * 2 - 1);
    lazy.resize(n * 2 - 1);
    isupd.resize(n * 2 - 1);
  }
  void prop(int num, int s) {
    if (isupd[num]) {
      data[num] = PROP()(data[num], lazy[num], 1, s);
      if (num < n - 1) {
        lazy[num * 2 + 1] = PROP()(lazy[num * 2 + 1], lazy[num]);
        lazy[num * 2 + 2] = PROP()(lazy[num * 2 + 2], lazy[num]);
        isupd[num * 2 + 1] = 1;
        isupd[num * 2 + 2] = 1;
      }
      lazy[num] = T();
      isupd[num] = 0;
    }
  }
  void op(int a, int b, T v, int num = 0, int base = 1) {
    int l = (num + 1 - base) * (n / base), r = l + n / base;
    prop(num, r - l);
    if (a == l && b == r) {
      isupd[num] = 1;
      lazy[num] = PROP()(lazy[num], v);
      prop(num, r - l);
    } else {
      int nr = (l + r) / 2;
      if (nr > a) op(a, min(b, nr), v, num * 2 + 1, base * 2);
      if (nr < b) op(max(a, nr), b, v, num * 2 + 2, base * 2);
      prop(num * 2 + 1, (r - l) / 2), prop(num * 2 + 2, (r - l) / 2);
      data[num] = OP()(data[num * 2 + 1], data[num * 2 + 2]);
    }
  }
  T query(int a, int b, int num = 0, int base = 1) {
    int l = (num + 1 - base) * (n / base), r = l + n / base;
    prop(num, r - l);
    if (a == l && b == r)
      return data[num];
    else {
      int nr = (l + r) / 2;
      T ret = T();
      if (nr > a) ret = OP()(ret, query(a, min(b, nr), num * 2 + 1, base * 2));
      if (nr < b) ret = OP()(ret, query(max(a, nr), b, num * 2 + 2, base * 2));
      return ret;
    }
  }
};
template <class T>
class ADD {
 public:
  T operator()(const T a, const T b, const int ra = 1, int rb = 1) {
    return a * ra + b * rb;
  }
};
template <class T>
class UPD {
 public:
  T operator()(const T a, const T b, const int ra = 1, int rb = 1) { return b; }
};
template <class T>
class RMQ {
 public:
  T operator()(const T a, const T b) { return min(a, b); }
};
template <class T>
class SUM {
 public:
  T operator()(const T a, const T b) { return a + b; }
};
struct N {
 public:
  long long num;
  N(long long num) : num(num) {}
  N() : num(0) {}
  N operator+(const N obj) const { return N(obj.num + num); }
  N operator*(const N obj) const { return N(obj.num * num); }
  bool operator<(const N obj) const { return obj.num > num; }
};
int main(void) {
  int n, m;
  cin >> n >> m;
  vector<vector<Edge>> g(n);
  for (int i = (0); (m) > i; i++) {
    int a, b;
    scanf("%d %d", &a, &b);
    a--, b--;
    g[a].push_back({a, b, 1});
    g[b].push_back({b, a, 1});
  }
  vector<pair<int, int>> circle;
  vector<int> visited(n, -1);
  int vn = 0;
  stack<int> st;
  function<void(int, int)> dfs = [&](int c, int p) {
    if (visited[c] != -1) {
      if (visited[c] < visited[p]) {
        stack<int> buf;
        int Min = INT_MAX, Max = INT_MIN;
        while (1) {
          int cur = st.top();
          buf.push(cur);
          st.pop();
          Min = min(Min, cur);
          Max = max(Max, cur);
          if (cur == c) break;
        }
        circle.push_back({Min, Max});
        while (buf.size()) st.push(buf.top()), buf.pop();
      }
      return;
    }
    visited[c] = vn;
    vn++;
    st.push(c);
    for (auto itr : g[c])
      if (itr.to != p) dfs(itr.to, c);
    st.pop();
  };
  for (int i = (0); (n) > i; i++) {
    if (visited[i] == -1) dfs(i, -1);
  }
  vector<int> kyo(n);
  set<pair<int, int>> cir;
  for (auto itr : circle) cir.insert({itr.second, itr.first});
  sort((circle).begin(), (circle).end());
  int cc = 0;
  for (int i = (0); (n) > i; i++) {
    if (cir.size() == 0) {
      kyo[i] = n;
    } else
      kyo[i] = cir.begin()->first;
    for (; circle.size() > cc; cc++) {
      if (circle[cc].first > i) break;
      cir.erase({circle[cc].second, circle[cc].first});
    }
  }
  vector<long long> rui(n + 1);
  for (int i = (0); (n) > i; i++) {
    rui[i + 1] = rui[i] + (kyo[i] - i);
  }
  int q;
  cin >> q;
  for (int i = (0); (q) > i; i++) {
    int l, r;
    scanf("%d %d", &l, &r);
    l--;
    int m = lower_bound(kyo.begin() + l, kyo.end(), r) - kyo.begin();
    long long ans = rui[min(r, m)] - rui[l];
    if (rui[min(r, m)] - rui[l] < 0) return 1;
    if (m < r) ans += ((r * 1LL - m) + 1) * (r - m) / 2;
    printf("%lld\n", ans);
  }
  return 0;
}

```