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 MAX = 1 << 19;
vector<int> V[MAX];
vector<pair<int, int> > Ciklus;
int bio[MAX], kad[MAX], par[MAX], vr = 1;
int n, m;
pair<pair<int, int>, int> q[MAX];
vector<int> Desne[MAX];
int dokle[MAX];
long long rje[MAX];
pair<int, int> cik(int node, int gor) {
  int mn = node, mx = node;
  for (;;) {
    assert(par[node] != -1);
    node = par[node];
    mn = min(mn, node);
    mx = max(mx, node);
    if (node == gor) break;
  }
  return pair<int, int>(mn, mx);
}
void dfs(int node, int pr) {
  bio[node] = 1;
  kad[node] = vr++;
  par[node] = pr;
  for (auto it : V[node]) {
    if (bio[it]) {
      if (it == pr || kad[it] > kad[node]) continue;
      Ciklus.push_back(cik(node, it));
    } else
      dfs(it, node);
  }
}
void find_cycles() {
  for (int i = 0; i < n; i++)
    if (!bio[i]) dfs(i, -1);
}
void gen_dokle() {
  int td = n - 1;
  for (int i = n - 1; i >= 0; i--) {
    for (auto it : Desne[i]) td = min(td, it - 1);
    dokle[i] = td;
  }
}
void stavi(long long fn[MAX], int pos, long long val) {
  for (pos += 3; pos < MAX; pos += pos & -pos) fn[pos] += val;
}
long long vrati(long long fn[MAX], int pos) {
  long long ret = 0;
  for (pos += 3; pos; pos -= pos & -pos) ret += fn[pos];
  return ret;
}
long long fen_sum[MAX], fen_kol[MAX], sum_lev[MAX];
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    a--;
    b--;
    V[a].push_back(b);
    V[b].push_back(a);
  }
  find_cycles();
  int brq;
  scanf("%d", &brq);
  for (int i = 0; i < brq; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    a--;
    b--;
    q[i] = make_pair(pair<int, int>(a, b), i);
  }
  sort(q, q + brq,
       [](pair<pair<int, int>, int> a, pair<pair<int, int>, int> b) {
         return a.first.second < b.first.second;
       });
  for (auto it : Ciklus) Desne[it.first].push_back(it.second);
  gen_dokle();
  for (int i = 0; i < n; i++) stavi(sum_lev, i, i);
  for (int i = 0; i < n; i++) stavi(fen_kol, i, 1);
  int inddokle = 0;
  for (int i = 0; i < brq; i++) {
    for (; inddokle < n && dokle[inddokle] <= q[i].first.second; inddokle++) {
      stavi(fen_sum, inddokle, dokle[inddokle] - inddokle + 1);
      stavi(fen_kol, inddokle, -1);
      stavi(sum_lev, inddokle, -inddokle);
    }
    long long mojval = vrati(fen_sum, q[i].first.second) -
                       vrati(fen_sum, q[i].first.first - 1);
    mojval += ((long long)q[i].first.second + 1) *
                  (vrati(fen_kol, q[i].first.second) -
                   vrati(fen_kol, q[i].first.first - 1)) -
              (vrati(sum_lev, q[i].first.second) -
               vrati(sum_lev, q[i].first.first - 1));
    rje[q[i].second] = mojval;
  }
  for (int i = 0; i < brq; i++) printf("%lld\n", rje[i]);
  return 0;
}
