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·10^{5}$, $1 ≤ *m* ≤ 3·10^{5}$) — 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 $*a*_{*i*}$ and $*b*_{*i*}$ ($1 ≤ *a*_{*i*}, *b*_{*i*} ≤ *n*$; $*a*_{*i*} ≠ *b*_{*i*}$), denoting an edge between vertices $*a*_{*i*}$ and $*b*_{*i*}$. 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·10^{5}$) — the number of queries.

The next $*q*$ lines contain queries. The $*i*$-th of these lines contains two integers $*l*_{*i*}$ and $*r*_{*i*}$ ($1 ≤ *l*_{*i*} ≤ *r*_{*i*} ≤ *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*]$ ($*l*_{*i*} ≤ *x* ≤ *y* ≤ *r*_{*i*}$), such that the graph that only includes vertices from segment $[*x*; *y*]$ and edges between them is bipartite.

Note

The first example is shown on the picture below:

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: