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;
using ll = long long;
using pii = pair<int, int>;
template <class T>
using V = vector<T>;
template <class T>
using VV = V<V<T>>;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }
template <class T, class U>
void chmin(T& t, const U& u) {
  if (t > u) t = u;
}
template <class T, class U>
void chmax(T& t, const U& u) {
  if (t < u) t = u;
}
template <class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
  os << "(" << p.first << "," << p.second << ")";
  return os;
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  os << "{";
  for (int i = 0; i < (v.size()); i++) {
    if (i) os << ",";
    os << v[i];
  }
  os << "}";
  return os;
}
const int maxn = 300010;
V<int> g[maxn];
bool vis[maxn];
int par[maxn];
V<pii> cycles;
int dep[maxn];
void dfs(int v, int p, int d) {
  vis[v] = true;
  dep[v] = d;
  par[v] = p;
  for (int to : g[v])
    if (to != p) {
      if (vis[to]) {
        cycles.emplace_back(minmax(v, to));
      } else {
        dfs(to, v, d + 1);
      }
    }
}
int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  for (int i = 0; i < (m); i++) {
    int a, b;
    scanf("%d %d", &a, &b);
    --a;
    --b;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  for (int i = 0; i < (n); i++)
    if (!vis[i]) {
      dfs(i, -1, 0);
    }
  sort((cycles).begin(), (cycles).end());
  cycles.erase(unique((cycles).begin(), (cycles).end()), cycles.end());
  V<int> tor(n, n + 1);
  for (auto e : cycles) {
    true;
    int mini = min(e.first, e.second), maxi = max(e.first, e.second);
    int p = e.first, q = e.second;
    if (dep[p] < dep[q]) swap(p, q);
    while (dep[p] > dep[q]) {
      p = par[p];
      chmin(mini, p);
      chmax(maxi, p);
    }
    while (p != q) {
      p = par[p];
      q = par[q];
      chmin(mini, min(p, q));
      chmax(maxi, max(p, q));
    }
    true;
    chmin(tor[mini], maxi);
  }
  for (int i = n - 2; i >= 0; --i) {
    chmin(tor[i], tor[i + 1]);
  }
  int q;
  scanf("%d", &q);
  V<ll> pref(n + 1);
  for (int i = 0; i < (n); i++) {
    pref[i + 1] = pref[i] + tor[i];
  }
  while (q--) {
    int l, r;
    scanf("%d %d", &l, &r);
    --l;
    int p = lower_bound(tor.begin() + l, tor.begin() + r, r) - tor.begin();
    ll ans =
        (pref[p] - pref[l]) + ll(r) * (r - p) - (ll)(l + r - 1) * (r - l) / 2;
    printf("%lld\n", ans);
  }
  return 0;
}
