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 = 3e5 + 10;
int rd() {
  int x = 0, w = 1;
  char ch = 0;
  while (ch < '0' || ch > '9') {
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = (x << 3) + (x << 1) + (ch ^ 48);
    ch = getchar();
  }
  return x * w;
}
int to[N << 1], nt[N << 1], hd[N], tot = 1;
void adde(int x, int y) {
  ++tot, to[tot] = y, nt[tot] = hd[x], hd[x] = tot;
  ++tot, to[tot] = x, nt[tot] = hd[y], hd[y] = tot;
}
int fa[N], ch[N][2];
bool tg[N];
bool nrt(int x) { return ch[fa[x]][0] == x || ch[fa[x]][1] == x; }
void rev(int x) {
  if (x) swap(ch[x][0], ch[x][1]), tg[x] ^= 1;
}
void psdn(int x) {
  if (tg[x]) rev(ch[x][0]), rev(ch[x][1]), tg[x] = 0;
}
void ppush(int x) {
  if (nrt(x)) ppush(fa[x]);
  psdn(x);
}
void rot(int x) {
  int y = fa[x], z = fa[y], yy = ch[y][1] == x, w = ch[x][!yy];
  if (nrt(y)) ch[z][ch[z][1] == y] = x;
  ch[x][!yy] = y, ch[y][yy] = w;
  if (w) fa[w] = y;
  fa[y] = x, fa[x] = z;
}
void spl(int x) {
  ppush(x);
  while (nrt(x)) {
    int y = fa[x], z = fa[y];
    if (nrt(y)) ((ch[y][1] == x) ^ (ch[z][1] == y)) ? rot(x) : rot(y);
    rot(x);
  }
}
void acs(int x) {
  for (int y = 0; x; y = x, x = fa[x]) spl(x), ch[x][1] = y;
}
void mkrt(int x) { acs(x), spl(x), rev(x); }
int fdrt(int x) {
  acs(x), spl(x), psdn(x);
  while (ch[x][0]) x = ch[x][0], psdn(x);
  return x;
}
void split(int x, int y) { mkrt(x), acs(y), spl(y); }
void link(int x, int y) { split(x, y), fa[x] = y; }
void cut(int x, int y) { split(x, y), fa[x] = ch[y][0] = 0; }
void dl(int x, int l, int r) {
  for (int i = hd[x]; i; i = nt[i]) {
    int y = to[i];
    if (y >= l && y <= r) cut(x, y);
  }
}
int n, m, va[N];
long long sf[N];
int sh(int ql, int qr) {
  int l = ql, r = qr;
  while (l <= r) {
    int mid = (l + r) >> 1;
    if (va[mid] >= qr)
      r = mid - 1;
    else
      l = mid + 1;
  }
  return r + 1;
}
long long s1(int x) { return 1ll * x * (x + 1) / 2; }
int main() {
  n = rd(), m = rd();
  for (int i = 1; i <= m; ++i) adde(rd(), rd());
  for (int l = 1, r = 1; r <= n; ++r) {
    for (int i = hd[r]; i;) {
      int y = to[i];
      if (y >= l && y <= r) {
        if (fdrt(r) == fdrt(y)) {
          va[l] = r - 1, dl(l, l + 1, r), ++l;
          continue;
        }
        link(r, y);
      }
      i = nt[i];
    }
    if (r == n) {
      while (l <= n) va[l] = r, ++l;
    }
  }
  for (int i = 1; i <= n; ++i) sf[i] = sf[i - 1] + va[i];
  int q = rd();
  while (q--) {
    int l = rd(), r = rd(), p = sh(l, r);
    printf("%lld\n", sf[p - 1] - sf[l - 1] - (s1(p - 1) - s1(l - 1)) + (p - l) +
                         s1(r - p + 1));
  }
  return 0;
}
