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.* ; import java.util.* ; import java.math.* ;
import static java.lang.Math.min ;
import static java.lang.Math.max ;

public class Codeshefcode{
	public static void main(String[] args) throws IOException{
		/*Solver Machine = new Solver() ;
		Machine.Solve() ; Machine.Finish() ;*/
		new Thread(null,new Runnable(){
			public void run(){
				Solver Machine = new Solver() ;
				try{
					Machine.Solve() ; Machine.Finish() ;
				}catch(Exception e){
					e.printStackTrace() ; System.out.flush() ;
					System.exit(-1) ;
				}catch(Error e){
					e.printStackTrace() ; System.out.flush() ;
					System.exit(-1) ;
				}
			}
		},"Solver",1l<<27).start() ;
	}
}

class mylist extends ArrayList<Integer>{}
class myset extends TreeSet<Integer>{}
class mystack extends Stack<Integer>{}
class mymap extends TreeMap<Long,Integer>{}

class pair implements Comparable<pair>{
	int x ; int y ; 
	pair(int x,int y){ this.x=x ; this.y=y ;} 
	public int compareTo(pair p){
		return (this.x<p.x ? -1 : (this.x>p.x ? 1 : (this.y<p.y ? -1 : (this.y>p.y ? 1 : 0)))) ;
	}
}

class Solver{
	Reader ip = new Reader(System.in) ;	  
	PrintWriter op = new PrintWriter(System.out) ;
	mylist adj[] ;
	int mrk=0 ;
	int par[] ;
	int cyc[] ;
	public void Solve() throws IOException{
		int n = ip.i() ;
		int m = ip.i() ;
		adj =  new mylist[n+1] ;
		par = new int[n+1] ;
		cyc = new int[n+1] ;
		Arrays.fill(cyc,-1) ;
		for(int i=1 ; i<=n ; i++) adj[i] = new mylist() ;
		for(int i=1 ; i<=m ; i++){
			int u = ip.i() ;
			int v = ip.i() ;
			adj[u].add(v) ;
			adj[v].add(u) ;
		}
		for(int i=1 ; i<=n ; i++) if(par[i]==0) dfs(i,new myset()) ;
		int lw[] = new int[mrk] ;
		int hg[] = new int[mrk] ;
		Arrays.fill(lw,Integer.MAX_VALUE) ;
		Arrays.fill(hg,Integer.MIN_VALUE) ;
		for(int i=1 ; i<=n ; i++){
			if(cyc[i]==-1) continue ;
			lw[cyc[i]] = min(lw[cyc[i]],i) ;
			hg[cyc[i]] = max(hg[cyc[i]],i) ;
		}
		int lim[] = new int[n+1] ;
		Arrays.fill(lim,n+1) ;
		for(int i=1 ; i<=n ; i++){
			if(cyc[i]==-1) continue ;
			if(i==lw[cyc[i]]) lim[i] = hg[cyc[i]] ;
		}
		for(int i=n ; i>=1 ; i--)
			lim[i] = min(lim[i],i==n ? n+1 : lim[i+1]) ;
		long clim[] = new long[n+1] ;
		for(int i=1 ; i<=n ; i++) clim[i] = clim[i-1]+lim[i] ;
		int q = ip.i() ;
		while(q--!=0){
			int l = ip.i() ;
			int r = ip.i() ;
			int idx = Arrays.binarySearch(lim,l,r+1,r+1) ;
			if(idx<0) idx = -idx-1 ;
			long res = (clim[idx-1]-clim[l-1])-(((idx-l)*(l+idx-1l))/2) ;
			res+=(((r-idx+1l)*(r-idx+2))/2) ;
			pln(res) ; 
		}
	}
	void dfs(int nd,myset anc){
		for(int chd : adj[nd]){
			if(chd==par[nd]) continue ;
			if(par[chd]==0){
				anc.add(nd) ;
				par[chd]=nd ;
				dfs(chd,anc) ;
				anc.remove(nd) ;
			}else if(cyc[chd]==-1){
				mylist cnd = new mylist() ;
				int itr=nd ;
				while(itr!=chd){
					cnd.add(itr) ;
					itr = par[itr] ;
				}
				cnd.add(chd) ;
				for(int elem : cnd) cyc[elem]=mrk ;
				mrk++ ;
			}
		}
	}
	void Finish(){ op.flush();	op.close(); }
	void p(Object o){ op.print(o) ; }
	void pln(Object o){ op.println(o) ;}		
}

class Mod{
	static long mod=1000000007 ;
	static long d(long a,long b){ return (a*inv(b))%mod ; }
	static long m(long a,long b){ return (a*b)%mod ; }
	static long inv(long a){ return pow(a,mod-2) ; }
	static long pow(long a,long b){
		if(b<0) return pow(inv(a),-b) ;
		long val=a ; long ans=1 ;
		while(b!=0){
			if((b&1)==1) ans = (ans*val)%mod ; 
			val = (val*val)%mod ; 
			b/=2 ;
		}
		return ans ;
	}	
}
class Reader{
	BufferedReader reader;
	StringTokenizer tkz;
	Reader(InputStream input) {
		reader = new BufferedReader(new InputStreamReader(input)) ;
		tkz = new StringTokenizer("") ;
	}
	String s() throws IOException{
		while (!tkz.hasMoreTokens()) tkz = new StringTokenizer(reader.readLine()) ;
		return tkz.nextToken() ;
	}
	int i() throws IOException{ return Integer.parseInt(s()) ;}
	long l() throws IOException{ return Long.parseLong(s()) ;}
	double d() throws IOException{	return Double.parseDouble(s()) ;}
}