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

public class E902{

	// 8 9 2 7 7 4 4 2 1 4 1 3 3 5 5 6 6 8 1 8
	// 13 15 8 7 7 6 7 13 13 6 1 13 1 12 1 2 12 9 9 1 11 9 3 11 11 4 10 5 5 4 10 3
	// 5 6 1 2 2 3 3 1 3 4 4 5 5 3
	// 7 9 1 2 2 3 3 1 1 4 4 5 5 1 1 6 6 7 7 1
	// 7 9 7 1 1 2 2 7 7 3 3 4 4 7 7 5 5 6 6 7

	void solve() 
	{
		int n = ni(), m = ni();
		int[] v1 = new int[m];
		int[] v2 = new int[m];
		for(int i=0;i<m;i++)
		{
			v1[i] = ni() - 1;
			v2[i] = ni() - 1;
		}
		int[][] g = buildUG(n, v1, v2);
		int[] vis = new int[n];
		int[] rch = new int[n];
		Arrays.fill(vis, -1);
		Arrays.fill(rch, n-1);
		int[] path = new int[n];
		for(int i=0;i<n;i++)
			if(vis[i] == -1)
				dfs(g, i, -1, path, new int[1], vis, rch);
				
		for(int i=n-2;i>=0;i--)
			rch[i] = Math.min(rch[i+1] ,rch[i]);
			
		long[] cml = new long[n+1];
		for(int i=0;i<n;i++)
			cml[i+1] = cml[i] + rch[i] - i + 1;
			
		int Q = ni();
		while(Q-->0)
		{
			int l = ni() - 1, r = ni() - 1;
			int sp = safePoint(rch, l, r);
			long ans = (long)(r - sp + 1) * (r - sp + 2) / 2 + cml[sp] - cml[l];
			out.println(ans);
		}
		
	}
	
	int safePoint(int[] rch, int L, int R)
	{
		int l = L, r = R;
		while(l < r)
		{
			int mid = l + r >> 1;
			if(rch[mid] < R)
				l = mid + 1;
			else
				r = mid;
		}
		return l;
	}
	
	void dfs(int[][] g, int cur, int par, int[] path, int[] ptr, int[] vis, int[] rch)
	{
		vis[cur] = -2;
		path[ptr[0]++] = cur;
		for(int nex : g[cur]) if(nex != par)
		{
			if(vis[nex] == -2 || vis[nex] == nex)
			{
				int min = -1>>>1;
				int max = 1<<31;
				for(int i=ptr[0]-1;i>=0;i--)
				{
					min = Math.min(path[i], min);
					max = Math.max(path[i], max);
					vis[path[i]] = nex;
					if(path[i] == nex)
						break;
				}
				rch[min] = max - 1;
			}
			else if(vis[nex] == -1)
				dfs(g, nex, cur, path, ptr, vis, rch);
		}
		ptr[0]--;
	}
	
	public int[][] buildUG(int n,int[] v1,int[] v2)
	{
		int[][] graph = new int[n][];
		int[] cn = new int[graph.length];
		for(int i=0;i<v1.length;i++)
		{
			cn[v1[i]]++;
			cn[v2[i]]++;
		}
		for(int i=0;i<graph.length;i++)
			graph[i] = new int[cn[i]];
		for(int i=0;i<v1.length;i++)
		{
			graph[v1[i]][--cn[v1[i]]] = v2[i];
			graph[v2[i]][--cn[v2[i]]] = v1[i];
		}
		return graph;
	}
	
	public static void main(String[] args){new E902().run();}
	
	private byte[] bufferArray = new byte[1024];
	private int bufLength = 0;
	private int bufCurrent = 0;
	InputStream inputStream;
	PrintWriter out;
	
	public void run()
	{
		inputStream = System.in;
		out = new PrintWriter(System.out);
		solve();
		out.flush();
	}
	
	int nextByte()
	{
		if(bufLength == -1)
			throw new InputMismatchException();
		if(bufCurrent >= bufLength)
		{
			bufCurrent = 0;
			try
			{bufLength = inputStream.read(bufferArray);}
			catch(IOException e)
			{ throw new InputMismatchException();}
			if(bufLength <= 0)
				return -1;
		}
		return bufferArray[bufCurrent++];
	}
	
	boolean isSpaceChar(int x)	{return (x < 33 || x > 126);}
	
	boolean isDigit(int x)	{return (x >= '0' && x <= '9');}
	
	int nextNonSpace()
	{
		int x;
		while((x=nextByte()) != -1 && isSpaceChar(x));
		return x;
	}
	
	int ni()
	{
		long ans = nl();
		if (ans >= Integer.MIN_VALUE && ans <= Integer.MAX_VALUE)
			return (int)ans;
		throw new InputMismatchException();
	}
	
	long nl()
	{
		long ans = 0;
		boolean neg = false;
		int x = nextNonSpace();
		if(x == '-') 
		{
			neg = true;
			x = nextByte();
		}
		while(!isSpaceChar(x))
		{
			if(isDigit(x))
			{
				ans = ans * 10 + x -'0';
				x = nextByte();
			}
			else
				throw new InputMismatchException();
		}
		return neg ? -ans : ans;
	}
	
	String ns()
	{
		StringBuilder sb = new StringBuilder();
		int x = nextNonSpace();
		while(!isSpaceChar(x))
		{
			sb.append((char)x);
			x = nextByte();
		}
		return sb.toString();
	}
	
	char nc()	{ return (char)nextNonSpace();}
	
	double nd()	{ return (double)Double.parseDouble(ns()); }
	
	char[] ca()	{ return ns().toCharArray();}
	
	char[][] ca(int n)
	{
		char[][] ans = new char[n][];
		for(int i=0;i<n;i++)
			ans[i] = ca();
		return ans;
	}
	
	int[] ia(int n)
	{
		int[] ans = new int[n];
		for(int i=0;i<n;i++)
			ans[i] = ni();
		return ans;
	}
	
	void db(Object... o) {System.out.println(Arrays.deepToString(o));}
	
}
