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>
#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T>
inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
class UnionFind {
 private:
  int n;
  vector<int> parent, r;
  int _find(int x) {
    if (parent[x] == x)
      return x;
    else
      return parent[x] = _find(parent[x]);
  }
  void _unite(int x, int y) {
    x = _find(x);
    y = _find(y);
    if (x == y) return;
    if (r[x] < r[y])
      parent[x] = y;
    else {
      parent[y] = x;
      if (r[x] == r[y]) r[x]++;
    }
  }

 public:
  int find(int x) { return _find(x); }
  void unite(int x, int y) { return _unite(x, y); }
  int operator[](int i) { return find(i); }
  UnionFind() : n(0) {}
  explicit UnionFind(size_t _n) : n(_n) {
    parent = vector<int>(n);
    r = vector<int>(n);
    for (int i = 0; i < n; i++) {
      parent[i] = i;
      r[i] = 0;
    }
  }
};
class EBipartiteSegments {
 public:
  int N, M;
  vector<int> used, vec, mx, mn, cnt;
  vector<vector<int>> G;
  UnionFind uf;
  void input(std::istream& in, std::ostream& out) {
    ios_base::sync_with_stdio(false);
    in >> N >> M;
    G = vector<vector<int>>(N, vector<int>());
    uf = UnionFind(N);
    used = vector<int>(N, 0);
    cnt = vector<int>(N, 0);
    mx = vector<int>(N, -1);
    mn = vector<int>(N, N + 1);
    for (int(i) = (0); (i) < (M); ++(i)) {
      int a, b;
      in >> a >> b;
      a--, b--;
      G[a].push_back(b), G[b].push_back(a);
    }
  }
  void dfs(int s, int p) {
    used[s] = 1;
    vec.push_back(s), cnt[s] = 1;
    for (auto u : G[s]) {
      if (u == p) continue;
      if (cnt[u]) {
        int idx = (int)(vec).size() - 1;
        while (vec[idx] != u) {
          uf.unite(vec[idx], vec[idx - 1]);
          --idx;
        }
      } else if (used[u])
        continue;
      else
        dfs(u, s);
    }
    vec.pop_back(), cnt[s] = 0;
  }
  bool ok(int i, int j) {
    int u = mx[uf.find(j)], v = mn[uf.find(j)];
    if (u == v) return true;
    if (u > j) return true;
    if (v < i) return true;
    return false;
  }
  void solve(std::istream& in, std::ostream& out) {
    input(in, out);
    for (int(i) = (0); (i) < (N); ++(i)) {
      if (not used[i]) dfs(i, -1);
    }
    for (int(i) = (0); (i) < (N); ++(i)) {
      chmax(mx[uf.find(i)], i);
      chmin(mn[uf.find(i)], i);
    }
    int j = 0;
    vector<int> right(N);
    for (int(i) = (0); (i) < (N); ++(i)) {
      while (j < N and ok(i, j)) ++j;
      right[i] = j - 1;
    }
    vector<long long> sum(N + 1, 0);
    for (int(i) = (0); (i) < (N); ++(i)) sum[i + 1] = sum[i] + right[i];
    int Q;
    in >> Q;
    for (int(i) = (0); (i) < (Q); ++(i)) {
      long long l, r;
      in >> l >> r;
      l--, r--;
      long long ans =
          sum[r + 1] - sum[l] + l * (l - 1) / 2 - r * (r + 1) / 2 + r - l + 1;
      long long idx = max(
          l, 1LL * distance(right.begin(),
                            upper_bound((right).begin(), (right).end(), r)));
      if (idx <= r) ans += (r - idx + 1) * r - sum[r + 1] + sum[idx];
      printf("%lld\n", ans);
    }
  }
};
int main() {
  EBipartiteSegments solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  solver.solve(in, out);
  return 0;
}
