#include <bits/stdc++.h>
using namespace std;
void ga(int N, int *A) {
  for (int i(0); i < N; i++) scanf("%d", A + i);
}
struct nd {
  nd() : P(0), pp(0), f(0) {
    *C = C[1] = 0;
    fix();
  }
  nd *P, *C[2], *pp;
  int f;
  void fix() {
    if (*C) C[0]->P = this;
    if (C[1]) C[1]->P = this;
  }
  void psh() {
    if (!f) return;
    f = 0, swap(*C, C[1]);
    if (*C) C[0]->f ^= 1;
    if (C[1]) C[1]->f ^= 1;
  }
  int up() { return !P ? -1 : !(P->C[0] == this); }
  void zig(int c) {
    nd *X = C[c];
    if ((X->P = P)) P->C[up()] = X;
    C[c] = X->C[1 - c], X->C[1 - c] = this;
    fix();
    X->fix();
    if (P) P->fix();
    swap(pp, X->pp);
  }
  void zA(int c) {
    nd *X = C[c], *Y = X->C[c];
    if ((Y->P = P)) P->C[up()] = Y;
    C[c] = X->C[1 - c], X->C[c] = Y->C[1 - c], Y->C[1 - c] = X;
    X->C[1 - c] = this, fix(), X->fix(), Y->fix();
    if (P) P->fix();
    swap(pp, Y->pp);
  }
  void zB(int c) {
    nd *X = C[c], *Y = X->C[1 - c];
    if ((Y->P = P)) P->C[up()] = Y;
    C[c] = Y->C[1 - c], X->C[1 - c] = Y->C[c], Y->C[1 - c] = this;
    Y->C[c] = X, fix(), X->fix(), Y->fix();
    if (P) P->fix();
    swap(pp, Y->pp);
  }
  nd *splay() {
    for (psh(); P;) {
      if (P->P) P->P->psh();
      P->psh(), psh();
      int c1 = up(), c2 = P->up();
      if (!~c2)
        P->zig(c1);
      else if (c1 == c2)
        P->P->zA(c1);
      else
        P->P->zB(c2);
    }
    return this;
  }
  nd *lst() { return psh(), C[1] ? C[1]->lst() : splay(); }
  nd *fst() { return psh(), *C ? C[0]->fst() : splay(); }
};
struct lc {
  lc(int N) : cd(N) {}
  void lnk(int u, int v) {
    if (con(u, v)) return;
    rt(v), cd[v].pp = &cd[u];
  }
  void cut(int u, int v) {
    if (!con(u, v)) return;
    rt(u), cd[v].splay();
    if (cd[v].pp)
      cd[v].pp = 0;
    else
      cd[v].C[0] = cd[v].C[0]->P = 0, cd[v].fix();
  }
  bool con(int u, int v) {
    nd *nu = acc(u)->fst(), *nv = acc(v)->fst();
    return nu == nv;
  }
  void rt(int u) {
    acc(u), cd[u].splay();
    if (*cd[u].C)
      cd[u].C[0]->P = 0, cd[u].C[0]->f ^= 1, cd[u].C[0]->pp = &cd[u],
      cd[u].C[0] = 0, cd[u].fix();
  }
  nd *acc(int u) {
    nd *x, *pp;
    for (x = cd[u].splay(); x->pp; x = pp) {
      pp = x->pp->splay(), x->pp = 0;
      if (pp->C[1]) pp->C[1]->P = 0, pp->C[1]->pp = pp;
      pp->C[1] = x, pp->fix();
    }
    return x;
  }
  vector<nd> cd;
} T(3e5 + 5);
long long S[333333];
int N, M, a, b, I, V[333333];
vector<int> g[333333];
int gt(int b, int I) {
  return lower_bound(g[I].begin(), g[I].end(), b) - g[I].begin();
}
bool ok(int b, int I) {
  int J = gt(b, I), K = J - 1;
  while (++K < (int)g[I].size() && g[I][K] < I) {
    if (T.con(g[I][K], I)) {
      while (--K >= J) T.cut(g[I][K], I);
      return 0;
    }
    T.lnk(g[I][K], I);
  }
  return 1;
}
int main(void) {
  scanf("%d%d", &N, &M);
  for (int i(0); i < M; i++)
    scanf("%d%d", &a, &b), g[--a].push_back(--b), g[b].push_back(a);
  for (int i(0); i < N; i++) sort(g[i].begin(), g[i].end());
  for (int i(0); i < N; i++) {
    while (I < N && ok(i, I)) ++I;
    a = gt(i, i) - 1, S[i] = I - i + (i ? S[i - 1] : 0), V[i] = I;
    while (++a < (int)g[i].size() && g[i][a] < I) T.cut(i, g[i][a]);
  }
  int _;
  scanf("%d", &_);
  for (int i(0); i < _; i++) {
    scanf("%d%d", &a, &b), --a, --b, I = upper_bound(V, V + N, b) - V;
    if (I <= a)
      printf("%lld\n", ((b - a + 1) * (b - a + 1 + 1ll) / 2));
    else
      printf("%lld\n", ((b - I + 1) * (b - I + 1 + 1ll) / 2) +
                           (S[I - 1] - (a ? S[a - 1] : 0)));
  }
  return 0;
}

### Prompt

Your task is to create a cpp solution to the following problem:

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>

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
void ga(int N, int *A) {
  for (int i(0); i < N; i++) scanf("%d", A + i);
}
struct nd {
  nd() : P(0), pp(0), f(0) {
    *C = C[1] = 0;
    fix();
  }
  nd *P, *C[2], *pp;
  int f;
  void fix() {
    if (*C) C[0]->P = this;
    if (C[1]) C[1]->P = this;
  }
  void psh() {
    if (!f) return;
    f = 0, swap(*C, C[1]);
    if (*C) C[0]->f ^= 1;
    if (C[1]) C[1]->f ^= 1;
  }
  int up() { return !P ? -1 : !(P->C[0] == this); }
  void zig(int c) {
    nd *X = C[c];
    if ((X->P = P)) P->C[up()] = X;
    C[c] = X->C[1 - c], X->C[1 - c] = this;
    fix();
    X->fix();
    if (P) P->fix();
    swap(pp, X->pp);
  }
  void zA(int c) {
    nd *X = C[c], *Y = X->C[c];
    if ((Y->P = P)) P->C[up()] = Y;
    C[c] = X->C[1 - c], X->C[c] = Y->C[1 - c], Y->C[1 - c] = X;
    X->C[1 - c] = this, fix(), X->fix(), Y->fix();
    if (P) P->fix();
    swap(pp, Y->pp);
  }
  void zB(int c) {
    nd *X = C[c], *Y = X->C[1 - c];
    if ((Y->P = P)) P->C[up()] = Y;
    C[c] = Y->C[1 - c], X->C[1 - c] = Y->C[c], Y->C[1 - c] = this;
    Y->C[c] = X, fix(), X->fix(), Y->fix();
    if (P) P->fix();
    swap(pp, Y->pp);
  }
  nd *splay() {
    for (psh(); P;) {
      if (P->P) P->P->psh();
      P->psh(), psh();
      int c1 = up(), c2 = P->up();
      if (!~c2)
        P->zig(c1);
      else if (c1 == c2)
        P->P->zA(c1);
      else
        P->P->zB(c2);
    }
    return this;
  }
  nd *lst() { return psh(), C[1] ? C[1]->lst() : splay(); }
  nd *fst() { return psh(), *C ? C[0]->fst() : splay(); }
};
struct lc {
  lc(int N) : cd(N) {}
  void lnk(int u, int v) {
    if (con(u, v)) return;
    rt(v), cd[v].pp = &cd[u];
  }
  void cut(int u, int v) {
    if (!con(u, v)) return;
    rt(u), cd[v].splay();
    if (cd[v].pp)
      cd[v].pp = 0;
    else
      cd[v].C[0] = cd[v].C[0]->P = 0, cd[v].fix();
  }
  bool con(int u, int v) {
    nd *nu = acc(u)->fst(), *nv = acc(v)->fst();
    return nu == nv;
  }
  void rt(int u) {
    acc(u), cd[u].splay();
    if (*cd[u].C)
      cd[u].C[0]->P = 0, cd[u].C[0]->f ^= 1, cd[u].C[0]->pp = &cd[u],
      cd[u].C[0] = 0, cd[u].fix();
  }
  nd *acc(int u) {
    nd *x, *pp;
    for (x = cd[u].splay(); x->pp; x = pp) {
      pp = x->pp->splay(), x->pp = 0;
      if (pp->C[1]) pp->C[1]->P = 0, pp->C[1]->pp = pp;
      pp->C[1] = x, pp->fix();
    }
    return x;
  }
  vector<nd> cd;
} T(3e5 + 5);
long long S[333333];
int N, M, a, b, I, V[333333];
vector<int> g[333333];
int gt(int b, int I) {
  return lower_bound(g[I].begin(), g[I].end(), b) - g[I].begin();
}
bool ok(int b, int I) {
  int J = gt(b, I), K = J - 1;
  while (++K < (int)g[I].size() && g[I][K] < I) {
    if (T.con(g[I][K], I)) {
      while (--K >= J) T.cut(g[I][K], I);
      return 0;
    }
    T.lnk(g[I][K], I);
  }
  return 1;
}
int main(void) {
  scanf("%d%d", &N, &M);
  for (int i(0); i < M; i++)
    scanf("%d%d", &a, &b), g[--a].push_back(--b), g[b].push_back(a);
  for (int i(0); i < N; i++) sort(g[i].begin(), g[i].end());
  for (int i(0); i < N; i++) {
    while (I < N && ok(i, I)) ++I;
    a = gt(i, i) - 1, S[i] = I - i + (i ? S[i - 1] : 0), V[i] = I;
    while (++a < (int)g[i].size() && g[i][a] < I) T.cut(i, g[i][a]);
  }
  int _;
  scanf("%d", &_);
  for (int i(0); i < _; i++) {
    scanf("%d%d", &a, &b), --a, --b, I = upper_bound(V, V + N, b) - V;
    if (I <= a)
      printf("%lld\n", ((b - a + 1) * (b - a + 1 + 1ll) / 2));
    else
      printf("%lld\n", ((b - I + 1) * (b - I + 1 + 1ll) / 2) +
                           (S[I - 1] - (a ? S[a - 1] : 0)));
  }
  return 0;
}

```