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 N = 300005, M = N * 21 * 2;
vector<int> tree[N], g[N];
int U[N], V[N], vis[N], arr[N], T, dsu[N];
bool isbridge[N];
int adj(int u, int e) { return U[e] ^ V[e] ^ u; }
int f(int x) { return dsu[x] = (dsu[x] == x ? x : f(dsu[x])); }
void merge(int a, int b) { dsu[f(a)] = f(b); }
int dfs0(int u, int edge) {
  vis[u] = 1;
  arr[u] = T++;
  int dbe = arr[u];
  for (auto e : g[u]) {
    int w = adj(u, e);
    if (!vis[w])
      dbe = min(dbe, dfs0(w, e));
    else if (e != edge)
      dbe = min(dbe, arr[w]);
  }
  if (dbe == arr[u] && edge != -1)
    isbridge[edge] = true;
  else if (edge != -1)
    merge(U[edge], V[edge]);
  return dbe;
}
void buildBridgeTree(int n, int m) {
  for (int i = 1; i <= n; i++) dsu[i] = i;
  for (int i = 1; i <= n; i++)
    if (!vis[i]) dfs0(i, -1);
}
int comp[N];
map<int, int> compress;
int nxt[N];
vector<int> vec[N];
int brute(int l, int r) {
  int ans = 0;
  for (int i = l; i <= r; i++) ans += min(r + 1, nxt[i]) - i;
  return ans;
}
int lft[M], rgt[M];
long long val[M];
int cnt;
struct persistent_segtree {
  int root[N];
  persistent_segtree() { root[0] = 0; }
  void add(int v, int V, int rt, int newrt, int s = 0, int e = N) {
    val[newrt] = val[rt] + V;
    if (s == e) {
      return;
    }
    int mid = (s + e) >> 1;
    if (v <= mid) {
      rgt[newrt] = rgt[rt];
      lft[newrt] = ++cnt;
      add(v, V, lft[rt], lft[newrt], s, mid);
    } else {
      lft[newrt] = lft[rt];
      rgt[newrt] = ++cnt;
      add(v, V, rgt[rt], rgt[newrt], mid + 1, e);
    }
  }
  void add(int i, int v, int V) {
    root[i] = ++cnt;
    add(v, V, root[i - 1], root[i]);
  }
  long long get(int l, int r, int rt, int s = 0, int e = N) {
    if (!rt || l > e || s > r) return 0LL;
    if (s >= l && e <= r) return val[rt];
    int mid = (s + e) >> 1;
    return get(l, r, lft[rt], s, mid) + get(l, r, rgt[rt], mid + 1, e);
  }
  long long GET(int l, int r, int x, int y) {
    return get(x, y, root[r]) - get(x, y, root[l - 1]);
  }
} tree1, tree2;
long long sm(int n) { return (n * 1ll * (n + 1)) / 2; }
long long getV(int l, int r) {
  long long sub = sm(r) - sm(l - 1);
  long long sum1 = tree2.GET(l, r, r + 2, N);
  long long sum2 = tree1.GET(l, r, 0, r + 1);
  return sum2 + sum1 * (r + 1) - sub;
}
set<int> st;
int main() {
  int n, m, q;
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= m; i++) {
    scanf("%d %d", U + i, V + i);
    g[U[i]].push_back(i);
    g[V[i]].push_back(i);
  }
  buildBridgeTree(n, m);
  int CNT = 0;
  for (int i = 1; i <= n; i++) st.insert(f(i));
  for (int x : st) compress[x] = ++CNT;
  for (int i = 1; i <= n; i++) {
    comp[i] = compress[f(i)];
    vec[comp[i]].push_back(i);
    nxt[i] = n + 1;
  }
  for (int i = 1; i <= CNT; i++) {
    if (vec[i].size() > 1) nxt[vec[i][0]] = vec[i].back();
  }
  for (int i = n - 1; i >= 1; i--) nxt[i] = min(nxt[i], nxt[i + 1]);
  for (int i = 1; i <= n; i++) {
    tree1.add(i, nxt[i], nxt[i]);
    tree2.add(i, nxt[i], 1);
  }
  scanf("%d", &(q));
  while (q--) {
    int l, r;
    scanf("%d %d", &l, &r);
    printf("%lld\n", getV(l, r));
  }
}
