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;
class SCC_BI {
 public:
  static const int MV = 310000;
  int NV, time;
  vector<vector<int>> E;
  vector<int> ord, llink, inin;
  stack<int> roots, S;
  vector<int> M;
  vector<int> ART;
  vector<vector<int>> SC;
  vector<pair<int, int>> BR;
  void init(int NV = MV) {
    this->NV = NV;
    E.clear();
    E.resize(NV);
  }
  void add_edge(int x, int y) {
    assert(NV);
    E[x].push_back(y);
    E[y].push_back(x);
  }
  void dfs(int cur, int pre) {
    int art = 0, conn = 0, i, se = 0;
    ord[cur] = llink[cur] = ++time;
    S.push(cur);
    inin[cur] = 1;
    roots.push(cur);
    for (i = 0; i < (E[cur].size()); i++) {
      int tar = E[cur][i];
      if (ord[tar] == 0) {
        conn++;
        dfs(tar, cur);
        llink[cur] = min(llink[cur], llink[tar]);
        art += (pre != -1 && ord[cur] <= llink[tar]);
        if (ord[cur] < llink[tar])
          BR.push_back(make_pair(min(cur, tar), max(cur, tar)));
      } else if (tar != pre || se) {
        llink[cur] = min(llink[cur], ord[tar]);
        while (inin[tar] && ord[roots.top()] > ord[tar]) roots.pop();
      } else
        se++;
    }
    if (cur == roots.top()) {
      SC.push_back(vector<int>());
      while (1) {
        i = S.top();
        S.pop();
        inin[i] = 0;
        SC.back().push_back(i);
        M[i] = SC.size() - 1;
        if (i == cur) break;
      }
      sort(SC.back().begin(), SC.back().end());
      roots.pop();
    }
    if (art || (pre == -1 && conn > 1)) ART.push_back(cur);
  }
  void scc() {
    SC.clear(), BR.clear(), ART.clear(), M.resize(NV);
    ord.clear(), llink.clear(), inin.clear(), time = 0;
    ord.resize(NV);
    llink.resize(NV);
    inin.resize(NV);
    for (int i = 0; i < NV; i++)
      if (!ord[i]) dfs(i, -1);
    sort(BR.begin(), BR.end());
    sort(ART.begin(), ART.end());
  }
};
SCC_BI bi;
int N, M, Q;
int R[303030];
int X[303030], Y[303030];
signed long long ret[303030];
const int DI = 600;
vector<pair<int, int>> ev[600];
int del[303030];
void solve() {
  int i, j, k, l, r, x, y;
  string s;
  scanf("%d%d", &N, &M);
  bi.init(N);
  for (i = 0; i < (M); i++) {
    scanf("%d%d", &x, &y);
    bi.add_edge(x - 1, y - 1);
  }
  for (i = 0; i < (N); i++) R[i] = N - 1;
  bi.scc();
  for (i = 0; i < (bi.SC.size()); i++)
    if (bi.SC[i].size() > 1) {
      sort((bi.SC[i].begin()), (bi.SC[i].end()));
      R[bi.SC[i][0]] = bi.SC[i].back() - 1;
    }
  for (i = N - 2; i >= 0; i--) R[i] = min(R[i], R[i + 1]);
  scanf("%d", &Q);
  for (i = 0; i < (Q); i++) {
    scanf("%d%d", &X[i], &Y[i]);
    X[i]--, Y[i]--;
    ev[X[i] / DI].push_back({Y[i], i});
  }
  for (i = 0; i < (DI); i++)
    if (ev[i].size()) {
      memset(del, 0, sizeof(del));
      sort((ev[i].begin()), (ev[i].end()));
      int cnt = 0;
      signed long long tot = 0;
      int LL = 0, RR = -1;
      for (auto& e : ev[i]) {
        while (RR < e.first) {
          RR++;
          cnt++;
          tot += cnt;
          del[R[RR]]++;
          cnt -= del[RR];
        }
        while (LL > X[e.second]) {
          LL--;
          if (R[LL] <= RR) {
            tot += R[LL] - LL + 1;
          } else {
            cnt++;
            tot += RR - LL + 1;
            del[R[LL]]++;
          }
        }
        while (LL < X[e.second]) {
          if (R[LL] <= RR) {
            tot -= R[LL] - LL + 1;
          } else {
            cnt--;
            tot -= RR - LL + 1;
            del[R[LL]]--;
          }
          LL++;
        }
        ret[e.second] = tot;
      }
    }
  for (i = 0; i < (Q); i++) cout << ret[i] << endl;
}
int main(int argc, char** argv) {
  string s;
  int i;
  if (argc == 1) ios::sync_with_stdio(false), cin.tie(0);
  for (i = 0; i < (argc - 1); i++) s += argv[i + 1], s += '\n';
  for (i = 0; i < (s.size()); i++) ungetc(s[s.size() - 1 - i], stdin);
  cout.tie(0);
  solve();
  return 0;
}
