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.util.*;
import java.io.*;
import java.math.*;
public class A{

    void solve(){

        int n=ni(),m=ni();
        graph=new ArrayList[n+1];
        for(int i=1;i<=n;i++) graph[i]=new ArrayList<>();
        while(m-->0){
            int a=ni(),b=ni();
            graph[a].add(b); graph[b].add(a);
        }
        vis=new boolean[n+1];
        vis2=new boolean[n+1];

        a=new int[n+1];
        Arrays.fill(a,n);
        for(int i=1;i<=n;i++)
            if(!vis[i])
        dfs(i,-1);

        for(int i=n-1;i>=1;i--) a[i]=Math.min(a[i+1],a[i]);
       //  for(int i=1;i<=n;i++) pw.print(a[i]+" ");
        long sum[]=new long[n+1];
        for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i]-i+1;
       // tree=new long[4*n+1];
        int q=ni();
       // build(1,1,n);
        while(q-->0){
            int l=ni(),r=ni();
            int id=upper_bound(a,n,r,l,r);
            long ans=0;
            long d=r-id+1;
            if(id<l) ans=(d*(d+1))/2;
            else if(id>=l && id<=r) ans=sum[id-1]-sum[l-1]+(d*(d+1))/2;
            else ans=sum[r]-sum[l-1];
            pw.println(ans);
        }


    }

    long tree[];

        void build(int node,int l,int r){
        if(l==r){
            tree[node]=a[l]-l+1;

        }else {
            int mid = (l + r) / 2;
            build(2 * node, l, mid);
            build(2 * node + 1, mid+1, r);
            tree[node] = tree[2 * node] + tree[2 * node + 1];
        }
    }

    long sum(int x,int y,int id,int l,int r){
            if(l>r) return 0;
        if(y<l || x>r) return 0;
        if(l>=x && r<=y) return tree[id];
        int mid=(l+r)/2;
        return sum(x,y,2*id,l,mid)+sum(x,y,2*id+1,mid+1,r);
    }
    int upper_bound(int a[],int n,int x,int ll,int rr){
        int l=ll,h=rr;
        while(l<=h){
            int mid=(l+h)/2;

            if(x>=a[mid]) l=mid+1;
            else h=mid-1;
        }
        return l;
    }
    ArrayList<Integer> graph[];
    boolean vis[];
    boolean vis2[];
    int a[];
    Stack<Integer> stk=new Stack<>();
    Stack<Integer> stk2=new Stack<>();

    void dfs(int v,int pr){
       // pw.println(v);
        if(vis2[v]){
            int mn=Integer.MAX_VALUE,mx=-1;
            stk2.clear();
            while(true) {
                int u=stk.pop();
                mn = Math.min(mn, u);
                mx = Math.max(mx, u);
                stk2.push(u);
                if(u==v) break;
            }
            while(!stk2.isEmpty()) stk.push(stk2.pop());

            if(mn!=Integer.MAX_VALUE)
            a[mn]=Math.min(a[mn],mx-1);
          //  if(v==7) pw.println(mn+" "+mx);
        }
        if(vis[v]) return;
        vis2[v]=true;
        vis[v]=true;
        stk.push(v);
        for(int u : graph[v]){
            if(u!=pr) dfs(u,v);
        }
        stk.pop();
        vis2[v]=false;
    }


    long M=(long)1e9+7;
    InputStream is;
    PrintWriter pw;
    String INPUT = "";
    void run() throws Exception {
        is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
        pw = new PrintWriter(System.out);
        long s = System.currentTimeMillis();
        solve();
        pw.flush();
        if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
    }

    public static void main(String[] args) throws Exception { new A().run(); }

    private byte[] inbuf = new byte[1024];
    public int lenbuf = 0, ptrbuf = 0;

    private int readByte() {
        if(lenbuf == -1)throw new InputMismatchException();
        if(ptrbuf >= lenbuf){
            ptrbuf = 0;
            try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
            if(lenbuf <= 0)return -1;
        }
        return inbuf[ptrbuf++];
    }

    private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
    private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }

    private double nd() { return Double.parseDouble(ns()); }
    private char nc() { return (char)skip(); }

    private String ns() {
        int b = skip();
        StringBuilder sb = new StringBuilder();
        while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    private char[] ns(int n) {
        char[] buf = new char[n];
        int b = skip(), p = 0;
        while(p < n && !(isSpaceChar(b))){
            buf[p++] = (char)b;
            b = readByte();
        }
        return n == p ? buf : Arrays.copyOf(buf, p);
    }

    private char[][] nm(int n, int m) {
        char[][] map = new char[n][];
        for(int i = 0;i < n;i++)map[i] = ns(m);
        return map;
    }

    private int[] na(int n) {
        int[] a = new int[n];
        for(int i = 0;i < n;i++)a[i] = ni();
        return a;
    }

    private int ni() {
        int num = 0, b;
        boolean minus = false;
        while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
        if(b == '-'){
            minus = true;
            b = readByte();
        }

        while(true){
            if(b >= '0' && b <= '9'){
                num = num * 10 + (b - '0');
            }else{
                return minus ? -num : num;
            }
            b = readByte();
        }
    }

    private long nl() {
        long num = 0;
        int b;
        boolean minus = false;
        while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
        if(b == '-'){
            minus = true;
            b = readByte();
        }

        while(true){
            if(b >= '0' && b <= '9'){
                num = num * 10 + (b - '0');
            }else{
                return minus ? -num : num;
            }
            b = readByte();
        }
    }

    private void tr(Object... o) { if(INPUT.length() > 0)System.out.println(Arrays.deepToString(o)); }
}