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 MOD = 1e9 + 7;
const int C = 26;
void add(int &x, int y) {
  x += y;
  while (x >= MOD) x -= MOD;
  while (x < 0) x += MOD;
}
int fix(int x) {
  while (x >= MOD) x -= MOD;
  while (x < 0) x += MOD;
  return x;
}
int pw(int a, int b) {
  int ret = 1;
  while (b) {
    if (b & 1) ret = 1ll * ret * a % MOD;
    b >>= 1;
    a = 1ll * a * a % MOD;
  }
  return ret;
}
const int MAXN = 3e5 + 10;
struct fenw {
  long long ft[MAXN];
  fenw() { memset(ft, 0, sizeof(ft)); }
  void upd(int i, long long x) {
    for (i += 2; i < MAXN; i += i & -i) ft[i] += x;
  }
  long long qry(int i) {
    long long s = 0;
    for (i += 2; i; i -= i & -i) s += ft[i];
    return s;
  }
  long long qry(int l, int r) { return qry(r) - qry(l - 1); }
} ft1, ft2;
vector<int> adj[MAXN];
int n, m, minL[MAXN], par[MAXN], vis[MAXN];
void addCycle(int v, int u) {
  int mn = u, mx = u;
  while (v != u) {
    mn = min(mn, v);
    mx = max(mx, v);
    v = par[v];
  }
  minL[mx] = max(minL[mx], mn);
}
void dfs(int v) {
  if (~par[v]) adj[v].erase(find(adj[v].begin(), adj[v].end(), par[v]));
  vis[v] = 1;
  for (int u : adj[v]) {
    if (vis[u] == 1) {
      addCycle(v, u);
    } else if (!vis[u]) {
      par[u] = v;
      dfs(u);
    }
  }
  vis[v] = 2;
}
int l[MAXN], r[MAXN], sec[MAXN];
long long ans[MAXN];
void solve() {
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    --a;
    --b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  memset(minL, -1, sizeof(minL));
  memset(par, -1, sizeof(par));
  for (int i = 0; i < n; i++)
    if (!vis[i]) dfs(i);
  for (int i = 1; i < n; i++) minL[i] = max(minL[i], minL[i - 1]);
  int queries;
  cin >> queries;
  for (int i = 0; i < queries; i++) cin >> l[i] >> r[i], --l[i], --r[i];
  iota(sec, sec + queries, 0);
  sort(sec, sec + queries, [](int i, int j) { return r[i] < r[j]; });
  for (int i = 0, k = 0; i < queries; i++) {
    int j = sec[i];
    while (k <= r[j]) {
      ft1.upd(minL[k], minL[k]);
      ft2.upd(minL[k], 1);
      k++;
    }
    long long cnt_bad = ft2.qry(l[j] - 1) - l[j];
    long long sum_good = ft1.qry(l[j], r[j]);
    ans[j] +=
        (long long)r[j] * (r[j] + 1) / 2 - (long long)l[j] * (l[j] - 1) / 2;
    ans[j] -= sum_good;
    ans[j] -= (long long)(l[j] - 1) * cnt_bad;
  }
  for (int i = 0; i < queries; i++) {
    cout << ans[i] << "\n";
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int te = 1;
  for (int w = 1; w <= te; w++) {
    solve();
  }
  return 0;
}
