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;
template <typename... As>
struct tpl : public std::tuple<As...> {
  using std::tuple<As...>::tuple;
  tpl() {}
  tpl(std::tuple<As...> const& b) { std::tuple<As...>::operator=(b); }
  template <typename T = tuple<As...> >
  typename tuple_element<0, T>::type const& x() const {
    return get<0>(*this);
  }
  template <typename T = tuple<As...> >
  typename tuple_element<0, T>::type& x() {
    return get<0>(*this);
  }
  template <typename T = tuple<As...> >
  typename tuple_element<1, T>::type const& y() const {
    return get<1>(*this);
  }
  template <typename T = tuple<As...> >
  typename tuple_element<1, T>::type& y() {
    return get<1>(*this);
  }
  template <typename T = tuple<As...> >
  typename tuple_element<2, T>::type const& z() const {
    return get<2>(*this);
  }
  template <typename T = tuple<As...> >
  typename tuple_element<2, T>::type& z() {
    return get<2>(*this);
  }
  template <typename T = tuple<As...> >
  typename tuple_element<3, T>::type const& w() const {
    return get<3>(*this);
  }
  template <typename T = tuple<As...> >
  typename tuple_element<3, T>::type& w() {
    return get<3>(*this);
  }
};
using lli = long long int;
using llu = long long unsigned;
using pii = tpl<lli, lli>;
using piii = tpl<lli, lli, lli>;
using piiii = tpl<lli, lli, lli, lli>;
using vi = vector<lli>;
using vii = vector<pii>;
using viii = vector<piii>;
using vvi = vector<vi>;
using vvii = vector<vii>;
using vviii = vector<viii>;
template <class T>
using min_queue = priority_queue<T, vector<T>, greater<T> >;
template <class T>
using max_queue = priority_queue<T>;
template <size_t... I>
struct my_index_sequence {
  using type = my_index_sequence;
  static constexpr array<size_t, sizeof...(I)> value = {{I...}};
};
namespace my_index_sequence_detail {
template <typename I, typename J>
struct concat;
template <size_t... I, size_t... J>
struct concat<my_index_sequence<I...>, my_index_sequence<J...> >
    : my_index_sequence<I..., (sizeof...(I) + J)...> {};
template <size_t N>
struct make_index_sequence
    : concat<typename make_index_sequence<N / 2>::type,
             typename make_index_sequence<N - N / 2>::type>::type {};
template <>
struct make_index_sequence<0> : my_index_sequence<> {};
template <>
struct make_index_sequence<1> : my_index_sequence<0> {};
}  // namespace my_index_sequence_detail
template <class... A>
using my_index_sequence_for =
    typename my_index_sequence_detail::make_index_sequence<sizeof...(A)>::type;
template <class T, size_t... I>
void print_tuple(ostream& s, T const& a, my_index_sequence<I...>) {
  using swallow = int[];
  (void)swallow{0, (void(s << (I == 0 ? "" : ", ") << get<I>(a)), 0)...};
}
template <class T>
ostream& print_collection(ostream& s, T const& a);
template <class... A>
ostream& operator<<(ostream& s, tpl<A...> const& a);
template <class... A>
ostream& operator<<(ostream& s, tuple<A...> const& a);
template <class A, class B>
ostream& operator<<(ostream& s, pair<A, B> const& a);
template <class T, size_t I>
ostream& operator<<(ostream& s, array<T, I> const& a) {
  return print_collection(s, a);
}
template <class T>
ostream& operator<<(ostream& s, vector<T> const& a) {
  return print_collection(s, a);
}
template <class T, class U>
ostream& operator<<(ostream& s, multimap<T, U> const& a) {
  return print_collection(s, a);
}
template <class T>
ostream& operator<<(ostream& s, multiset<T> const& a) {
  return print_collection(s, a);
}
template <class T, class U>
ostream& operator<<(ostream& s, map<T, U> const& a) {
  return print_collection(s, a);
}
template <class T>
ostream& operator<<(ostream& s, set<T> const& a) {
  return print_collection(s, a);
}
template <class T>
ostream& print_collection(ostream& s, T const& a) {
  s << '[';
  for (auto it = begin(a); it != end(a); ++it) {
    s << *it;
    if (it != prev(end(a))) s << " ";
  }
  return s << ']';
}
template <class... A>
ostream& operator<<(ostream& s, tpl<A...> const& a) {
  s << '(';
  print_tuple(s, a, my_index_sequence_for<A...>{});
  return s << ')';
}
template <class... A>
ostream& operator<<(ostream& s, tuple<A...> const& a) {
  s << '(';
  print_tuple(s, a, my_index_sequence_for<A...>{});
  return s << ')';
}
template <class A, class B>
ostream& operator<<(ostream& s, pair<A, B> const& a) {
  return s << "(" << get<0>(a) << ", " << get<1>(a) << ")";
}
namespace link_cut {
struct node {
  node() {}
  node(lli cost_) : cost(cost_) { mcost = cost; }
  lli cost;
  lli mcost;
  node *p = 0, *cs[2] = {0, 0};
  bool isroot() const { return !p || (this != p->cs[0] && this != p->cs[1]); }
  lli dir() const { return this == p->cs[1]; }
  bool flip = 0;
};
void push(node* n) {
  if (n->flip) {
    swap(n->cs[0], n->cs[1]);
    for (lli i = 0; i < (lli)(2); ++i)
      if (n->cs[i]) n->cs[i]->flip ^= 1;
    n->flip = 0;
  }
}
void update(node* n) {
  if (n) {
    n->mcost = n->cost;
    for (lli i = 0; i < (lli)(2); ++i)
      if (n->cs[i]) n->mcost = min(n->mcost, n->cs[i]->mcost);
  }
}
void rotate(node* n) {
  lli d = n->dir();
  node *p = n->p, *b = n->cs[1 - d];
  if (!p->isroot()) p->p->cs[p->dir()] = n;
  n->p = p->p;
  n->cs[1 - d] = p;
  p->p = n;
  p->cs[d] = b;
  if (b) b->p = p;
  update(n);
  update(p);
  update(n->p);
}
void splay(node* n) {
  push(n);
  while (!n->isroot()) {
    if (n->p->p) push(n->p->p);
    push(n->p);
    push(n);
    if (n->p->isroot()) {
      rotate(n);
    } else if (n->dir() == n->p->dir()) {
      rotate(n->p);
      rotate(n);
    } else {
      rotate(n);
      rotate(n);
    }
  }
}
node* leftmost(node* n) {
  while (n->cs[0]) n = n->cs[0];
  return n;
}
void splice(node* x) {
  push(x->p);
  x->p->cs[1] = x;
  update(x->p);
}
void expose(node* x) {
  {
    node* y = x;
    while (y) {
      splay(y);
      y = y->p;
    }
  }
  {
    node* y = x;
    while (y->p) {
      splice(y);
      y = y->p;
    }
  }
  splay(x);
}
void evert(node* n) {
  expose(n);
  if (n->cs[0]) {
    n->cs[0]->flip ^= 1;
    n->cs[0] = 0;
    update(n);
  }
}
void link(node* x, node* y) {
  evert(y);
  y->p = x;
}
void cut(node* x, node* y) {
  evert(x);
  expose(y);
  y->cs[0] = 0;
  x->p = 0;
  update(y);
}
node* root(node* n) {
  expose(n);
  return leftmost(n);
}
lli path(node* x, node* y) {
  evert(x);
  expose(y);
  return min(y->cs[0]->mcost, y->cost);
}
}  // namespace link_cut
const lli N = 500000;
link_cut::node A[N];
link_cut::node E[N];
lli F[N];
lli SF[N + 1];
lli R[N];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  lli n, m;
  cin >> n >> m;
  vvii G(n);
  for (lli i = 0; i < (lli)(m); ++i) {
    lli u, v;
    cin >> u >> v;
    --u;
    --v;
    G[u].push_back(make_tuple(v, i));
    G[v].push_back(make_tuple(u, i));
  }
  for (lli i = 0; i < (lli)(n); ++i) {
    A[i] = link_cut::node(i);
  }
  vi AC(n);
  vi EE(n);
  vi C;
  function<void(lli, lli)> dfs = [&](lli i, lli p) {
    EE[i] = 1;
    AC[i] = 1;
    C.push_back(i);
    for (auto e_ : G[i]) {
      lli j, e;
      tie(j, e) = e_;
      if (j == p) continue;
      if (AC[j]) {
        set<lli> cc;
        lli k = C.size() - 1;
        while (1) {
          cc.insert(C[k]);
          if (C[k] == j) break;
          --k;
        }
        lli u = *cc.begin(), v = *cc.rbegin();
        F[v] = max(F[v], u + 1);
      }
      if (!EE[j]) dfs(j, i);
    }
    C.pop_back();
    AC[i] = 0;
  };
  for (lli i = 0; i < (lli)(n); ++i)
    if (!EE[i]) dfs(i, -1);
  for (lli i = 0; i < (lli)(n - 1); ++i) F[i + 1] = max(F[i], F[i + 1]);
  for (lli i = 0; i < (lli)(n); ++i) {
    R[i] = (i == 0 ? 0 : R[i - 1]);
    while (R[i] < n && F[R[i]] <= i) R[i]++;
  }
  for (lli i = 0; i < (lli)(n); ++i) SF[i + 1] = SF[i] + (i - F[i] + 1);
  lli q;
  cin >> q;
  vi ANS(q);
  for (lli i = 0; i < (lli)(q); ++i) {
    lli l, r;
    cin >> l >> r;
    --l;
    --r;
    lli t = min(r + 1, R[l]);
    lli a = 0;
    a += ((t - l) * (t - l + 1)) / 2;
    if (t <= r) a += (SF[r + 1] - SF[t]);
    cout << a << '\n';
  }
  cout << flush;
  return 0;
}
