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 std::pair;
using std::set;
using std::sort;
using std::swap;
const int N = 300010;
int _w;
int min(int a, int b) { return a < b ? a : b; }
int n, m, q, ql[N], qr[N], qid[N];
long long ans[N];
namespace G {
int head[N], nxt[N * 2], to[N * 2], eid;
void init() {
  eid = 0;
  memset(head, -1, sizeof head);
}
void link(int u, int v) {
  to[eid] = v, nxt[eid] = head[u], head[u] = eid++;
  to[eid] = u, nxt[eid] = head[v], head[v] = eid++;
}
}  // namespace G
bool cmp(int i, int j) { return qr[i] < qr[j]; }
namespace SGT {
long long tag[N * 4], sum[N * 4], qv;
int ql, qr;
void _add(int o, int L, int R) {
  if (L >= ql && R <= qr) {
    tag[o] += qv;
    sum[o] += qv * (R - L + 1);
  } else {
    int M = (L + R) / 2, lc = o << 1, rc = lc | 1;
    if (ql <= M) _add(lc, L, M);
    if (qr > M) _add(rc, M + 1, R);
    sum[o] = sum[lc] + sum[rc] + tag[o] * (R - L + 1);
  }
}
void add(int l, int r, int v) {
  ql = l, qr = r, qv = v;
  _add(1, 1, n);
}
void _query(int o, int L, int R, long long add) {
  if (L >= ql && R <= qr) {
    qv += sum[o];
    qv += add * (R - L + 1);
  } else {
    int M = (L + R) / 2, lc = o << 1, rc = lc | 1;
    add += tag[o];
    if (ql <= M) _query(lc, L, M, add);
    if (qr > M) _query(rc, M + 1, R, add);
  }
}
long long query(int l, int r) {
  ql = l, qr = r, qv = 0;
  _query(1, 1, n, 0);
  return qv;
}
}  // namespace SGT
namespace LCT {
struct Node {
  Node *ch[2], *pa, *light;
  int id, minid, rev;
  Node(int v) {
    ch[0] = ch[1] = pa = light = NULL;
    id = minid = v, rev = 0;
  }
  int relation() { return this == pa->ch[0] ? 0 : 1; }
  Node *maintain() {
    minid = id;
    if (ch[0]) minid = min(minid, ch[0]->minid);
    if (ch[1]) minid = min(minid, ch[1]->minid);
    return this;
  }
  Node *pushdown() {
    if (rev) {
      rev = 0;
      swap(ch[0], ch[1]);
      if (ch[0]) ch[0]->rev ^= 1;
      if (ch[1]) ch[1]->rev ^= 1;
    }
    return this;
  }
  Node *rotate() {
    if (pa->pa) pa->pa->pushdown();
    pa->pushdown(), pushdown();
    Node *old = pa;
    int x = relation();
    if (pa->pa) pa->pa->ch[old->relation()] = this;
    pa = pa->pa;
    old->ch[x] = ch[x ^ 1];
    if (ch[x ^ 1]) ch[x ^ 1]->pa = old;
    ch[x ^ 1] = old, old->pa = this;
    swap(light, old->light);
    return old->maintain(), maintain();
  }
  Node *splay(Node *tar = NULL) {
    while (pa != tar) {
      if (pa->pa == tar)
        rotate();
      else {
        pa->pa->pushdown();
        pa->pushdown();
        if (relation() == pa->relation())
          pa->rotate(), rotate();
        else
          rotate(), rotate();
      }
    }
    return this;
  }
  Node *expose() {
    splay()->pushdown();
    if (!ch[1]) return this;
    ch[1]->light = this;
    ch[1]->pa = NULL;
    ch[1] = NULL;
    return maintain();
  }
  bool splice() {
    splay();
    if (!light) return false;
    light->expose();
    light->ch[1] = this;
    pa = light;
    light = NULL;
    pa->maintain();
    return true;
  }
  Node *access() {
    expose();
    while (splice())
      ;
    return this;
  }
  Node *evert() {
    access()->splay()->rev ^= 1;
    return this;
  }
  Node *froot() {
    access()->splay();
    Node *o = this;
    while (o->pushdown()->ch[0]) o = o->ch[0];
    return o->splay();
  }
};
Node *nod[N];
void init() {
  for (int i = 1; i <= n; ++i) nod[i] = new Node(i);
}
bool connect(int u, int v) { return nod[u]->froot() == nod[v]->froot(); }
void link(int u, int v) { nod[u]->evert()->light = nod[v]; }
int query(int u, int v) {
  nod[u]->evert();
  return nod[v]->access()->splay()->minid;
}
void cut(int u, int v) {
  nod[u]->evert();
  nod[v]->access();
  nod[u]->expose();
  nod[v]->light = NULL;
}
}  // namespace LCT
set<pair<int, int> > edge;
void erase(int u) {
  using namespace G;
  for (int i = head[u]; ~i; i = nxt[i]) {
    int v = to[i];
    if (edge.count(pair<int, int>(u, v))) {
      edge.erase(pair<int, int>(u, v));
      LCT::cut(u, v);
    }
  }
}
void update(int &L, int &R) {
  using namespace G;
  ++R;
  for (int i = head[R]; ~i; i = nxt[i]) {
    int v = to[i];
    if (v >= L && v <= R) {
      if (LCT::connect(v, R)) {
        int tmp = LCT::query(v, R);
        while (L <= tmp) erase(L++);
        if (v >= L && v <= R) {
          LCT::link(v, R);
          edge.insert(pair<int, int>(v, R));
        }
      } else {
        LCT::link(v, R);
        edge.insert(pair<int, int>(v, R));
      }
    }
  }
  SGT::add(L, R, 1);
}
int main() {
  _w = scanf("%d%d", &n, &m);
  G::init();
  for (int i = 0; i < m; ++i) {
    int u, v;
    _w = scanf("%d%d", &u, &v);
    G::link(u, v);
  }
  _w = scanf("%d", &q);
  for (int i = 0; i < q; ++i) {
    _w = scanf("%d%d", ql + i, qr + i);
    qid[i] = i;
  }
  sort(qid, qid + q, cmp);
  LCT::init();
  int L = 1, R = 1;
  SGT::add(L, R, 1);
  for (int i = 0; i < q; ++i) {
    int id = qid[i];
    while (R < qr[id]) update(L, R);
    ans[id] = SGT::query(ql[id], qr[id]);
  }
  for (int i = 0; i < q; ++i) printf("%lld\n", ans[i]);
  return 0;
}
