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>
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;

/**
 * @author Don Li
 */
public class BipartiteSegments3 {
    
    int N = (int) 3e5 + 10;
    
    int n, m;
    int[][] G;
    
    int[] sta = new int[N];
    int[] par = new int[N];
    
    List<int[]> pairs = new ArrayList<>();
    
    void solve() {
        n = in.nextInt(); m = in.nextInt();
        int[] fr = new int[m], to = new int[m];
        for (int i = 0; i < m; i++) {
            fr[i] = in.nextInt() - 1;
            to[i] = in.nextInt() - 1;
        }
        G = build_graph(n, fr, to);
        
        for (int i = 0; i < n; i++) {
            if (sta[i] == 0) dfs(i, -1);
        }
        
        pairs.sort(Comparator.comparingInt(a -> a[0]));
        
        int[] mx = new int[n];
        for (int i = n - 1, j = pairs.size() - 1, limit = n; i >= 0; i--) {
            while (j >= 0 && pairs.get(j)[0] >= i) {
                limit = Math.min(limit, pairs.get(j)[1]);
                j--;
            }
            mx[i] = limit;
        }
    
        long[] sum = new long[n + 1];
        for (int i = 0; i < n; i++) sum[i + 1] = sum[i] + mx[i] - i;
    
        int Q = in.nextInt();
        while (Q-- > 0) {
            int l = in.nextInt() - 1, r = in.nextInt();
            int p = upperBound(mx, r);
            if (p <= l) {
                out.println((long) (r - l) * (r - l + 1) / 2);
                continue;
            }
            if (p >= r) {
                out.println(sum[r] - sum[l]);
                continue;
            }
            out.println(sum[p] - sum[l] + (long) (r - p) * (r - p + 1) / 2);
        }
    }
    
    int upperBound(int[] a, int k) {
        int lb = -1, ub = a.length;
        while (ub - lb > 1) {
            int m = (lb + ub) >> 1;
            if (a[m] > k) ub = m;
            else lb = m;
        }
        return ub;
    }
    
    void dfs(int u, int p) {
        sta[u] = 1;
        par[u] = p;
        for (int v : G[u]) {
            if (v != p) {
                if (sta[v] == 0) {
                    dfs(v, u);
                } else if (sta[v] == 1) {
                    int min = u, max = u;
                    for (int x = u; ; x = par[x]) {
                        min = Math.min(x, min);
                        max = Math.max(x, max);
                        if (x == v) break;
                    }
                    pairs.add(new int[]{min, max});
                }
            }
        }
        sta[u] = 2;
    }
    
    int[][] build_graph(int n, int[] from, int[] to) {
        int[][] G = new int[n][];
        int[] cnt = new int[n];
        for (int i = 0; i < from.length; i++) {
            cnt[from[i]]++;
            cnt[to[i]]++;
        }
        for (int i = 0; i < n; i++) G[i] = new int[cnt[i]];
        for (int i = 0; i < from.length; i++) {
            G[from[i]][--cnt[from[i]]] = to[i];
            G[to[i]][--cnt[to[i]]] = from[i];
        }
        return G;
    }
    
    public static void main(String[] args) {
        in = new FastScanner(new BufferedReader(new InputStreamReader(System.in)));
        out = new PrintWriter(System.out);
        new BipartiteSegments3().solve();
        out.close();
    }
    
    static FastScanner in;
    static PrintWriter out;
    
    static class FastScanner {
        BufferedReader in;
        StringTokenizer st;
        
        public FastScanner(BufferedReader in) {
            this.in = in;
        }
        
        public String nextToken() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(in.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        
        public int nextInt() {
            return Integer.parseInt(nextToken());
        }
        
        public long nextLong() {
            return Long.parseLong(nextToken());
        }
        
        public double nextDouble() {
            return Double.parseDouble(nextToken());
        }
    }
}
