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 int maxn = 310000;
long long cal(long long a, long long b) { return (a + b) * (b - a + 1ll) / 2; }
int n, m, q;
vector<int> V[maxn];
struct edge {
  int y, nex;
} a[maxn << 1];
int len, fir[maxn];
inline void ins(const int x, const int y) {
  a[++len] = (edge){y, fir[x]};
  fir[x] = len;
}
int dfn[maxn], id, dep[maxn], t[maxn];
void dfs(const int x, const int fa, const int dd) {
  dfn[x] = ++id;
  dep[x] = dd;
  t[dd] = x;
  for (int k = fir[x], y = a[k].y; k; k = a[k].nex, y = a[k].y)
    if (y != fa) {
      if (dep[y] < dep[x] && dfn[y]) {
        int mx = 1, mn = n;
        for (int j = dep[y]; j <= dep[x]; j++)
          mx = max(mx, t[j]), mn = min(mn, t[j]);
        V[mx].push_back(mn);
      } else if (!dfn[y])
        dfs(y, x, dd + 1);
    }
}
struct node {
  int l, r, i;
  friend inline bool operator<(const node x, const node y) { return x.r < y.r; }
} Q[maxn];
long long ans[maxn];
struct segment {
  long long b, k;
} seg[maxn << 2];
int lx, rx;
long long fb, fk;
void upd(const int x, const int l, const int r) {
  if (rx < l || r < lx) return;
  if (lx <= l && r <= rx) {
    seg[x].k += fk, seg[x].b += fb;
    return;
  }
  int mid = l + r >> 1, lc = x << 1, rc = lc | 1;
  upd(lc, l, mid);
  upd(rc, mid + 1, r);
}
long long re;
int loc;
void query(const int x, const int l, const int r, long long k, long long b) {
  k += seg[x].k, b += seg[x].b;
  if (l == r) {
    re = b - k * (long long)l;
    return;
  }
  int mid = l + r >> 1, lc = x << 1, rc = lc | 1;
  if (loc <= mid)
    query(lc, l, mid, k, b);
  else
    query(rc, mid + 1, r, k, b);
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    ins(x, y);
    ins(y, x);
  }
  for (int i = 1; i <= n; i++)
    if (!dfn[i]) dfs(i, 0, 1);
  scanf("%d", &q);
  for (int i = 1; i <= q; i++) scanf("%d%d", &Q[i].l, &Q[i].r), Q[i].i = i;
  sort(Q + 1, Q + q + 1);
  int now = 1, nowq = 1;
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < V[i].size(); j++) now = max(now, V[i][j] + 1);
    fb = i + 1ll, fk = 1ll, lx = now, rx = i;
    upd(1, 1, n);
    fb = i - now + 1, fk = 0;
    lx = 1, rx = now - 1;
    if (lx <= rx) upd(1, 1, n);
    while (nowq <= q && Q[nowq].r == i) {
      re = 0;
      loc = Q[nowq].l;
      query(1, 1, n, 0, 0);
      ans[Q[nowq].i] = re;
      nowq++;
    }
  }
  for (int i = 1; i <= q; i++) printf("%I64d\n", ans[i]);
  return 0;
}
