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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.ArrayList;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        CBipartiteSegments solver = new CBipartiteSegments();
        solver.solve(1, in, out);
        out.close();
    }

    static class CBipartiteSegments {
        int n;
        int m;
        ArrayList<Integer>[] edges;
        boolean[] visited;
        boolean[] used;
        int[] parent;
        int[] mx;
        int max;
        int min;
        int[] bit;
        long[] preSum;

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            n = in.readInt();
            m = in.readInt();
            edges = new ArrayList[n + 1];
            for (int i = 0; i <= n; i++) edges[i] = new ArrayList<>();
            visited = new boolean[n + 1];
            used = new boolean[n + 1];
            parent = new int[n + 1];
            mx = new int[n + 1];
            preSum = new long[n + 1];
            Arrays.fill(mx, n);
            bit = new int[n + 1];

            for (int i = 0; i < m; i++) {
                int u = in.readInt();
                int v = in.readInt();
                edges[u].add(v);
                edges[v].add(u);
            }
            for (int i = 1; i <= n; i++) {
                if (!used[i]) dfs(i, -1);
            }
            for (int i = n - 1; i >= 0; i--) {
                mx[i] = Math.min(mx[i], mx[i + 1]);
            }
            for (int i = 1; i <= n; i++) {
                preSum[i] = preSum[i - 1] + (mx[i] - i + 1);
            }
            int q = in.readInt();
            while (q-- > 0) {
                int l = in.readInt();
                int r = in.readInt();
                long ans = 0;

                int lo = l - 1, hi = r;
                while (lo < hi) {
                    int mid = (lo + hi + 1) / 2;
                    if (mx[mid] <= r) {
                        lo = mid;
                    } else {
                        hi = mid - 1;
                    }
                }
                ans += preSum[lo] - preSum[l - 1];
                long v = r - lo;
                ans += v * (v + 1) / 2;
                out.println(ans);
            }


        }

        void dfs(int pos, int p) {
            if (visited[pos]) {
                max = Integer.MIN_VALUE;
                min = Integer.MAX_VALUE;
                check(p, pos);
                return;
            }
            parent[pos] = p;
            visited[pos] = true;
            for (int i : edges[pos]) {
                if (i == p) continue;
                if (used[i]) continue;
                dfs(i, pos);
            }
            visited[pos] = false;
            used[pos] = true;
        }

        void check(int pos, int root) {

            int tt = 0;
            while (true) {
                max = Math.max(pos, max);
                min = Math.min(min, pos);
                if (pos == root) break;
                pos = parent[pos];
            }
            mx[min] = Math.min(max - 1, mx[min]);
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public int readInt() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return isWhitespace(c);
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }
}

