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.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Div1_453C {

	static ArrayList<Integer>[] aList;

	static int nV, nE;

	static int[] rMst;

	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter printer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
		StringTokenizer inputData = new StringTokenizer(reader.readLine());
		nV = Integer.parseInt(inputData.nextToken());
		nE = Integer.parseInt(inputData.nextToken());
		aList = new ArrayList[nV];

		for (int i = 0; i < nV; i++) {
			aList[i] = new ArrayList<>();
		}

		for (int i = 0; i < nE; i++) {
			inputData = new StringTokenizer(reader.readLine());
			int a = Integer.parseInt(inputData.nextToken()) - 1;
			int b = Integer.parseInt(inputData.nextToken()) - 1;
			aList[a].add(b);
			aList[b].add(a);
		}

		visited = new boolean[nV];
		processed = new boolean[nV];
		min = new int[nV];
		Arrays.fill(min, -1);
		for (int i = 0; i < nV; i++) {
			if (!visited[i]) {
				dfs(i, -1);
			}
		}

		rMst = new int[nV];
		for (int l = 0, r = 0; l < nV; l++) {
			while (r + 1 < nV && min[r + 1] < l) {
				r++;
			}
			rMst[l] = r;
		}

		long[] mPSum = new long[nV];
		mPSum[0] = rMst[0] + 1;
		for (int i = 1; i < nV; i++) {
			mPSum[i] = mPSum[i - 1] + rMst[i] - i + 1;
		}

		int nQ = Integer.parseInt(reader.readLine());

		while (nQ-- > 0) {
			inputData = new StringTokenizer(reader.readLine());
			int qL = Integer.parseInt(inputData.nextToken()) - 1;
			int qR = Integer.parseInt(inputData.nextToken()) - 1;
			int sep = binSearch(qR);
			long sum = 0;
			if (qL < sep) {
				sum += mPSum[Math.min(sep - 1, qR)] - (qL > 0 ? mPSum[qL - 1] : 0);
			}
			if (sep <= qR) {
				long n = qR - Math.max(sep, qL) + 1;
				sum += n * (n + 1) / 2;
			}
			printer.println(sum);
		}
		printer.close();
	}

	// finds first greater
	static int binSearch(int r) {
		int low = 0;
		int high = nV;

		while (low != high) {
			int mid = (low + high) / 2;
			if (rMst[mid] <= r) {
				low = mid + 1;
			} else {
				high = mid;
			}
		}
		return low;
	}

	static boolean[] visited;
	static boolean[] processed;

	static ArrayList<Integer> stack = new ArrayList<>();

	static int[] min;

	static void dfs(int cV, int pV) {
		visited[cV] = true;
		stack.add(cV);

		for (int aV : aList[cV]) {
			if (aV == pV) {
				continue;
			}
			if (!visited[aV]) {
				dfs(aV, cV);
			} else if (!processed[aV]) {
				assert (!processed[cV]);
				int cMin = Integer.MAX_VALUE;
				int cMax = 0;

				for (int i = stack.size() - 1; i >= 0; i--) {
					processed[stack.get(i)] = true;
					cMin = Math.min(cMin, stack.get(i));
					cMax = Math.max(cMax, stack.get(i));
					if (stack.get(i) == aV) {
						break;
					}
				}
				min[cMax] = cMin;
			}
		}
		stack.remove(stack.size() - 1);
	}
}
