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;
int n, m;
struct map {
  int s, t;
  int next;
} a[600101];
int edge;
int head[300101];
int scc, cnt;
bool v[300101];
int s[300101], top;
int dfn[300101], low[300101], belong[300101];
int fa[300101];
int indeg[300101], outdeg[300101];
inline void add(int s, int t) {
  a[edge].next = head[s];
  head[s] = edge;
  a[edge].s = s;
  a[edge].t = t;
}
inline int min(int x, int y) {
  if (x < y) return x;
  return y;
}
void tarjan(int d) {
  int i, x;
  cnt++;
  dfn[d] = cnt;
  low[d] = cnt;
  top++;
  s[top] = d;
  v[d] = true;
  for (i = head[d]; i != 0; i = a[i].next) {
    x = a[i].t;
    if (x == fa[d]) continue;
    fa[x] = d;
    if (dfn[x] == 0) {
      tarjan(x);
      low[d] = min(low[d], low[x]);
    } else if (v[x] && low[d] > dfn[x])
      low[d] = dfn[x];
  }
  if (dfn[d] == low[d]) {
    scc++;
    x = s[top];
    top--;
    while (x != d) {
      v[x] = false;
      belong[x] = scc;
      x = s[top];
      top--;
    }
    v[x] = false;
    belong[x] = scc;
  }
}
int ld[300101], rd[300101];
inline void count_edge() {
  memset(ld, 127 / 3, sizeof(ld));
  memset(rd, 0, sizeof(rd));
  int i;
  for (i = 1; i <= n; i++) {
    ld[belong[i]] = min(ld[belong[i]], i);
    rd[belong[i]] = max(rd[belong[i]], i);
  }
}
long long rr[300101];
long long ss[300101];
inline int findx(int l, int xx) {
  int r = n;
  while (l <= r) {
    int mid = (l + r) / 2;
    if (xx < rr[mid])
      r = mid - 1;
    else
      l = mid + 1;
  }
  return l;
}
int main() {
  scanf("%d%d", &n, &m);
  int i;
  int s, t;
  for (i = 1; i <= m; i++) {
    scanf("%d%d", &s, &t);
    edge++;
    add(s, t);
    edge++;
    add(t, s);
  }
  for (i = 1; i <= n; i++)
    if (dfn[i] == 0) tarjan(i);
  count_edge();
  int l = 1, r = 1;
  while (l <= n) {
    while ((ld[belong[r]] < l || ld[belong[r]] == l && l == r ||
            r != rd[belong[r]] || ld[belong[r]] == rd[belong[r]]) &&
           r <= n)
      r++;
    rr[l] = r - 1;
    l++;
    while (r <= l) r++;
  }
  for (i = 1; i <= n; i++) ss[i] = ss[i - 1] + (long long)(rr[i] - i + 1);
  int q;
  scanf("%d", &q);
  for (i = 1; i <= q; i++) {
    scanf("%d%d", &l, &r);
    int d = findx(l, r);
    long long ans = ss[d - 1] - ss[l - 1];
    ans += (long long)(r - d + 2) * (long long)(r - d + 1) / 2LL;
    printf("%I64d\n", ans);
  }
  return 0;
}
