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;
inline int rd() {
  register int res = 0, f = 1;
  register char c = getchar();
  while (!isdigit(c)) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (isdigit(c)) {
    res = (res << 1) + (res << 3) + c - '0';
    c = getchar();
  }
  return res * f;
}
int n, m, q;
struct edge {
  int to, nxt;
} e[300010 << 1];
int edgenum = 0;
int lin[300010] = {0};
void add(int a, int b) {
  e[++edgenum] = (edge){b, lin[a]};
  lin[a] = edgenum;
  e[++edgenum] = (edge){a, lin[b]};
  lin[b] = edgenum;
  return;
}
int dfn[300010], low[300010], tot = 0;
stack<int> s;
int minv[300010], maxv[300010], dcc = 0;
int f[300010];
long long sum[300010];
void tarjan(int k) {
  dfn[k] = low[k] = ++tot;
  s.push(k);
  for (int i = lin[k]; i != 0; i = e[i].nxt) {
    if (dfn[e[i].to] == 0) {
      tarjan(e[i].to);
      low[k] = min(low[k], low[e[i].to]);
      if (low[e[i].to] >= dfn[k]) {
        ++dcc;
        minv[dcc] = maxv[dcc] = k;
        int t;
        int cnt = 1;
        do {
          t = s.top();
          s.pop();
          minv[dcc] = min(minv[dcc], t);
          maxv[dcc] = max(maxv[dcc], t);
          ++cnt;
        } while (t != e[i].to);
        if (cnt != 2) f[minv[dcc]] = maxv[dcc] - 1;
      }
    } else {
      low[k] = min(low[k], dfn[e[i].to]);
    }
  }
  return;
}
long long calc(int L, int R) {
  int l = L - 1, r = R, mid;
  while (l < r) {
    mid = ((l + r + 1) >> 1);
    if (f[mid] <= R)
      l = mid;
    else
      r = mid - 1;
  }
  return (sum[l] - sum[L - 1] + 1ll * (R - l) * R) -
         1ll * (L + R - 2) * (R - L + 1) / 2;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; ++i) add(rd(), rd());
  for (int i = 1; i <= n; ++i) f[i] = n;
  for (int i = 1; i <= n; ++i) {
    if (dfn[i] == 0) tarjan(i);
  }
  for (int i = n - 1; i >= 1; --i) {
    f[i] = min(f[i], f[i + 1]);
  }
  for (int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + f[i];
  int l, r;
  scanf("%d", &q);
  for (int i = 1; i <= q; ++i) {
    l = rd();
    r = rd();
    printf("%I64d\n", calc(l, r));
  }
  return 0;
}
