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.*;
public class EE {
	public static void main(String[] args)throws Throwable {
		MyScanner sc=new MyScanner();
		PrintWriter pw=new PrintWriter(System.out);
		
		n=sc.nextInt();
		adj=new ArrayList [n];
		for(int i=0;i<n;i++)
			adj[i]=new ArrayList<Integer>();
		m=sc.nextInt();
		edges=new Edge [m];
		for(int i=0;i<m;i++){
			int u=sc.nextInt()-1;
			int v=sc.nextInt()-1;
			edges[i]=new Edge(u, v);
			adj[u].add(i);
			adj[v].add(i);
		}
		findBridges();
		comp=new int [n];
		Arrays.fill(comp, -1);
		compSize=new int [n];
		vis=new boolean [n];
		counter=0;
		for(int i=0;i<n;i++)
			if(!vis[i]){
				dfs2(i);
				if(compSize[counter]==1){
					comp[i]=-1;
					compSize[counter]=0;
				}
				else
					counter++;
			}
		last=new int [n];
		Arrays.fill(last, n-1);
		int start=0;
		for(int i=0;i<n;i++){
			if(comp[i]!=-1){
				compSize[comp[i]]--;
				while(start<=i && compSize[comp[i]]==0){
					if(comp[start]!=-1)
						compSize[comp[start]]++;
					last[start++]=i-1;
				}
			}
		}
		int q=sc.nextInt();
		Edge [] queries=new Edge [q];
		long [] ans=new long [q];
		for(int i=0;i<q;i++){
			int l=sc.nextInt()-1;
			int r=sc.nextInt()-1;
			queries[i]=new Edge(l, r, i);
		}
		Arrays.sort(queries);
		int p=0;
		ftSum=new long [n+1];
		ftCnt=new int [n+1];
		for(int i=n-1;i>=0;i--){
			update(last[i]+1, last[i]);
			while(p<q && queries[p].from==i){
				int l=queries[p].from;
				int r=queries[p].to;
				int idx=queries[p].idx;
				int cnt=getCnt(r+1);
				long sum=getSum(r+1);
				if(i>0){
					cnt-=getCnt(i);
					sum-=getSum(i);
				}
				ans[idx]+=sum;
				ans[idx]+=1L*(r-l+1-cnt)*r;
				ans[idx]+=(r-l+1);
				ans[idx]-=(1L*r*(r+1)/2);
				ans[idx]+=(1L*l*(l-1)/2);
				p++;
			}
		}
		
		for(long x : ans)
			pw.println(x);
		pw.flush();
		pw.close();
	}
	
	static long [] ftSum;
	static int [] ftCnt;
	
	static void update(int idx,int val){
		while(idx<=n){
			ftSum[idx]+=val;
			ftCnt[idx]++;
			idx+=(idx & -idx);
		}
	}
	
	static int getCnt(int idx){
		int ans=0;
		while(idx>0){
			ans+=ftCnt[idx];
			idx-=(idx &-idx);
		}
		return ans;
	}
	
	static long getSum(int idx){
		long ans=0;
		while(idx>0){
			ans+=ftSum[idx];
			idx-=(idx &-idx);
		}
		return ans;
	}
	
	static int [] last;
	static boolean [] vis;
	static int [] comp,compSize;
	
	static void dfs2(int u){
		vis[u]=true;
		compSize[counter]++;
		comp[u]=counter;
		for(int i : adj[u]){
			if(edges[i].isBridge)
				continue;
			int v=edges[i].from;
			if(v==u)
				v=edges[i].to;
			if(!vis[v])
				dfs2(v);
		}
	}
	
	static Edge [] edges;
	static ArrayList<Integer>[] adj;
	static int[] dfs_low, dfs_num, parent;
	static int n, m, counter;

	static void findBridges()
	{
		dfs_low=new int [n];
		dfs_num=new int [n];
		parent=new int [n];
		for(int i = 0; i < n; ++i)
			if(dfs_num[i] == 0)
				dfs(i);
	}
	
	static void dfs(int u)
	{
		dfs_num[u] = dfs_low[u] = ++counter;
		for(int i: adj[u]){
			int v=edges[i].from;
			if(v==u)
				v=edges[i].to;
			if(dfs_num[v] == 0)
			{
				parent[v] = u;
				dfs(v);
				if(dfs_low[v] > dfs_num[u])
					edges[i].isBridge=true;
				dfs_low[u] = Math.min(dfs_low[v], dfs_low[u]);
			}
			else
				if(parent[u] != v)
					dfs_low[u] = Math.min(dfs_low[u], dfs_num[v]);
		}
	}
	
	static class Edge implements Comparable<Edge>{
		int from,to,idx;
		boolean isBridge;
		Edge(int f,int t){
			from=f;
			to=t;
		}
		Edge(int f,int t,int i){
			from=f;
			to=t;
			idx=i;
		}
		public int compareTo(Edge o) {
			return o.from-from;
		}
	}
	
	static class MyScanner {
		BufferedReader br;
		StringTokenizer st;
		public MyScanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {while (st == null || !st.hasMoreElements()) {
			try {st = new StringTokenizer(br.readLine());}
			catch (IOException e) {e.printStackTrace();}}
		return st.nextToken();}
		int nextInt() {return Integer.parseInt(next());}
		long nextLong() {return Long.parseLong(next());}
		double nextDouble() {return Double.parseDouble(next());}
		String nextLine(){String str = "";
		try {str = br.readLine();}
		catch (IOException e) {e.printStackTrace();}
		return str;}
	}
}