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.ArrayList;
import java.util.Collections;

/*
 *  Based on Daniel Sleator's implementation http://www.codeforces.com/contest/117/submission/860934
 *  https://sites.google.com/site/indy256/algo/link-cut-tree-connectivity
 */

public class lct {
    
    public static void main(String[] args) throws IOException{
    	BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    	PrintWriter out = new PrintWriter(System.out);
    	String[] line=  in.readLine().split(" ");
    	int n = Integer.parseInt(line[0]);
    	int m = Integer.parseInt(line[1]);
    	int[] dp = new int[n];
    	for(int i = 0; i<n; i++) {
    		dp[i] = n-1;
    	}
    	ArrayList<Integer>[] adj = new ArrayList[n];
    	for(int i = 0; i<n; i++) {
    		adj[i] = new ArrayList<Integer>();
    	}
    	for(int i = 0; i<m; i++) {
    		line = in.readLine().split(" ");
    		int a = Integer.parseInt(line[0])-1;
    		int b = Integer.parseInt(line[1])-1;
    		adj[a].add(b);
    		adj[b].add(a);
    	}
    	for(int i = 0; i<n; i++) {
    		Collections.sort(adj[i]);
    	}
    	Node[] ar = new Node[n];
    	for(int i = 0; i<n; i++) {
    		ar[i] = new Node();
    	}
    	int p1 = 0;
    	int p2 = 0;
    	while(p1<n) {
    		while(p2+1<n) {
    			p2++;
    			for(int j = 0; j<adj[p2].size(); j++) {
    				int v = adj[p2].get(j);
    				if(v>p2 || v<p1) {
    					continue;
    				}
    				while(connected(ar[p2],ar[v])) {
    					dp[p1] = p2-1;
    					for(int k = 0; k<adj[p1].size(); k++) {
    		    			int v2 = adj[p1].get(k);
    		    			if(connected(ar[p1],ar[v2])) {
    		    				cut(ar[p1],ar[v2]);
    		    			}
    		    		}
    					p1++;
    				}
					link(ar[p2],ar[v]);
    			}
    		}
    		dp[p1] = p2;
    		p1++;
    	}
    	long[] cumudp = new long[n+1];
    	long[] cumuind = new long[n+1];
    	for(int i = 1; i<=n; i++) {
    		cumudp[i] = cumudp[i-1]+(long)dp[i-1];
    		cumuind[i] = cumuind[i-1]+(long)(i-1);
    	}
    	int q = Integer.parseInt(in.readLine());
    	for(int z = 0; z<q; z++) {
    		line = in.readLine().split(" ");
    		int l = Integer.parseInt(line[0])-1;
    		int r = Integer.parseInt(line[1])-1;
    		if(dp[l]>r) {
    			long ans = (long)(r+1)*(long)(r-l+1)-(cumuind[r+1]-cumuind[l]);
    			out.println(ans);
    		}
    		else {
    			int low = l;
    			int high = r;
    			while(low<high) {
    				int mid = (low+high+1)/2;
    				if(dp[mid]<=r) {
    					low = mid;
    				}
    				else {
    					high = mid-1;
    				}
    			}
    			int mid = low+1;
    			long ans = 0L;
    			if(mid<=r) {
    				ans += (long)(r+1)*(long)(r-mid+1)-(cumuind[r+1]-cumuind[mid]);
    			}
    			ans += (cumudp[low+1]-cumudp[l])+(long)(low-l+1)-(cumuind[low+1]-cumuind[l]);
    			out.println(ans);
    		}
    	}
    	out.flush();
    }
    
    public static void link(Node x, Node y) {
        if (connected(x, y))
            throw new RuntimeException("error: x and y are already connected");
        makeRoot(x);
        x.parent = y;
     }
    
    public static void cut(Node x, Node y) {
        makeRoot(x);
        expose(y);
        if (y.right != x || x.left != null || x.right != null)
            throw new RuntimeException("error: no edge (x,y)");
        y.right.parent = null;
        y.right = null;
    }
    
    static void connect(Node ch, Node p, Boolean isLeftChild) {
        if (ch != null)
            ch.parent = p;
        if (isLeftChild != null) {
            if (isLeftChild)
                p.left = ch;
            else
                p.right = ch;
       }
    }
    
    static void rotate(Node x) {
        Node p = x.parent;
        Node g = p.parent;
        boolean isRootP = p.isRoot();
        boolean leftChildX = (x == p.left);
        // create 3 edges: (x.r(l),p), (p,x), (x,g)
        connect(leftChildX ? x.right : x.left, p, leftChildX);
        connect(p, x, !leftChildX);
        connect(x, g, !isRootP ? p == g.left : null);
    }
    
    static void splay(Node x) {
        while (!x.isRoot()) {
            Node p = x.parent;
            Node g = p.parent;
            if (!p.isRoot())
                g.push();
            p.push();
            x.push();
            if (!p.isRoot())
                rotate((x == p.left) == (p == g.left) ? p/*zig-zig*/ : x/*zig-zag*/);
            rotate(x);
        }
      x.push();
    }
    
    // makes node x the root of the virtual tree, and also x becomes the leftmost node in its splay tree
    static Node expose(Node x) {
        Node last = null;
        for (Node y = x; y != null; y = y.parent) {
            splay(y);
            y.left = last;
            last = y;
        }
        splay(x);
        return last;
    }
    
    public static void makeRoot(Node x) {
        expose(x);
        x.revert = !x.revert;
    }
    
    public static boolean connected(Node x, Node y) {
        if (x == y)
            return true;
        expose(x);
        // now x.parent is null
        expose(y);
        return x.parent != null;
    }
    
    public static class Node {
        Node left;
        Node right;
        Node parent;
        boolean revert;
        
        // tests whether x is a root of a splay tree
        boolean isRoot() {
            return parent == null || (parent.left != this && parent.right != this);
        }
        
        void push() {
            if (revert) {
                revert = false;
                Node t = left;
                left = right;
                right = t;
                if (left != null)   left.revert = !left.revert;
                if (right != null)  right.revert = !right.revert;
            }
        }
    }  
}