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;
const long long S = 600001;
const long long inf = 1 << 30;
struct SegmentTree {
  long long dat, add;
} t[300002 * 4];
long long head[300002], ver[300002 * 2], nxt[300002 * 2], l;
long long n, m, q, i, tim, dfn[300002], low[300002], top, s[300002], cnt,
    scc[300002], L[300002], R[300002], a[300002], sum[300002];
bool cut[300002 * 2];
long long read() {
  char c = getchar();
  long long w = 0;
  while (c < '0' || c > '9') c = getchar();
  while (c <= '9' && c >= '0') {
    w = w * 10 + c - '0';
    c = getchar();
  }
  return w;
}
void insert(long long x, long long y) {
  ver[l] = y;
  nxt[l] = head[x];
  head[x] = l;
  l++;
}
void Tarjan(long long x, long long pre) {
  dfn[x] = low[x] = ++tim;
  for (long long i = head[x]; i != -1; i = nxt[i]) {
    long long y = ver[i];
    if (!dfn[y]) {
      Tarjan(y, i);
      low[x] = min(low[x], low[y]);
      if (low[y] > dfn[x]) cut[i] = cut[i ^ 1] = 1;
    } else if (i != (pre ^ 1))
      low[x] = min(low[x], dfn[y]);
  }
}
void dfs(long long x) {
  scc[x] = cnt;
  L[cnt] = min(L[cnt], x);
  R[cnt] = max(R[cnt], x);
  for (long long i = head[x]; i != -1; i = nxt[i]) {
    if (cut[i]) continue;
    long long y = ver[i];
    if (!scc[y]) dfs(y);
  }
}
void update(long long p) { t[p].dat = min(t[p * 2].dat, t[p * 2 + 1].dat); }
void spread(long long p) {
  if (t[p].add != inf) {
    t[p * 2].add = min(t[p * 2].add, t[p].add);
    t[p * 2 + 1].add = min(t[p * 2 + 1].add, t[p].add);
    t[p * 2].dat = min(t[p * 2].dat, t[p].add);
    t[p * 2 + 1].dat = min(t[p * 2 + 1].dat, t[p].add);
    t[p].add = inf;
  }
}
void build(long long p, long long l, long long r) {
  t[p].add = t[p].dat = inf;
  if (l == r) return;
  long long mid = (l + r) / 2;
  build(p * 2, l, mid);
  build(p * 2 + 1, mid + 1, r);
}
void change(long long p, long long l, long long r, long long ql, long long qr,
            long long x) {
  if (ql <= l && r <= qr) {
    t[p].dat = min(t[p].dat, x);
    t[p].add = min(t[p].add, x);
    return;
  }
  long long mid = (l + r) / 2;
  spread(p);
  if (ql <= mid) change(p * 2, l, mid, ql, qr, x);
  if (qr > mid) change(p * 2 + 1, mid + 1, r, ql, qr, x);
  update(p);
}
long long ask(long long p, long long l, long long r, long long x) {
  if (l == r) return t[p].dat;
  long long mid = (l + r) / 2;
  spread(p);
  if (x <= mid) return ask(p * 2, l, mid, x);
  return ask(p * 2 + 1, mid + 1, r, x);
}
signed main() {
  memset(head, -1, sizeof(head));
  memset(L, 0x3f, sizeof(L));
  n = read();
  m = read();
  for (i = 1; i <= m; i++) {
    long long u = read(), v = read();
    insert(u, v);
    insert(v, u);
  }
  for (i = 1; i <= n; i++) {
    if (!dfn[i]) Tarjan(i, S);
  }
  for (i = 1; i <= n; i++) {
    if (!scc[i]) cnt++, dfs(i);
  }
  build(1, 1, n);
  for (i = 1; i <= cnt; i++) {
    if (R[i] != L[i]) change(1, 1, n, 1, L[i], R[i]);
  }
  for (i = 1; i <= n; i++) {
    a[i] = ask(1, 1, n, i);
    sum[i] = sum[i - 1] + a[i] - i;
  }
  q = read();
  for (i = 1; i <= q; i++) {
    long long x = read(), y = read();
    long long p = upper_bound(a + x, a + y + 1, y) - a - 1;
    long long num1 = sum[p] - sum[x - 1], num2 = y - p;
    printf("%lld\n", num1 + num2 * (num2 + 1) / 2);
  }
  return 0;
}
