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.
The first line contains two integers *n* and *m* (1 ≤ *n* ≤ 3·10<sup class="upper-index">5</sup>, 1 ≤ *m* ≤ 3·10<sup class="upper-index">5</sup>) — 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*<sub class="lower-index">*i*</sub> and *b*<sub class="lower-index">*i*</sub> (1 ≤ *a*<sub class="lower-index">*i*</sub>, *b*<sub class="lower-index">*i*</sub> ≤ *n*; *a*<sub class="lower-index">*i*</sub> ≠ *b*<sub class="lower-index">*i*</sub>), denoting an edge between vertices *a*<sub class="lower-index">*i*</sub> and *b*<sub class="lower-index">*i*</sub>. 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<sup class="upper-index">5</sup>) — the number of queries.

The next *q* lines contain queries. The *i*-th of these lines contains two integers *l*<sub class="lower-index">*i*</sub> and *r*<sub class="lower-index">*i*</sub> (1 ≤ *l*<sub class="lower-index">*i*</sub> ≤ *r*<sub class="lower-index">*i*</sub> ≤ *n*) — the query parameters.
The first example is shown on the picture below:

<img class="tex-graphics" src="https://espresso.codeforces.com/01e1d1999228f416613ff64b5d0e0cf984f150b1.png" style="max-width: 100.0%;max-height: 100.0%;"/>

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:

<img class="tex-graphics" src="https://espresso.codeforces.com/09b9227070585b8d5a7dff3cbc5f8535c260a595.png" style="max-width: 100.0%;max-height: 100.0%;"/>
from collections import defaultdict as di
n,m = [int(x) for x in input().split()]
coupl = [di(set),di(set),di(set)]
for i in range(m):
    a,b = [int(x)-1 for x in input().split()]
    coupl[-1][a].add(b)
    coupl[-1][b].add(a)

colors = [-1]*n

def try_color(node):
    if len(coupl[0][node])==0:
        return 0
    if len(coupl[1][node])==0:
        return 1
    return -1
    

reach = [-1]*n
next_to_color = 0
for ind in range(n):
    if next_to_color<n:
        pos_color = try_color(next_to_color)
        print('try to color',pos_color)
        while pos_color!=-1:

            neig = []
            for cop in coupl:
                for nei in cop[next_to_color]:
                    neig.append(nei)

            for nei in neig:
                coupl[-1][nei].remove(next_to_color)
                coupl[pos_color][nei].add(next_to_color)

            colors[next_to_color] = pos_color
            next_to_color += 1
            if next_to_color>=n:
                break
            pos_color = try_color(next_to_color)

    reach[ind] = next_to_color-1

    neig = []
    for cop in coupl:
        for nei in cop[ind]:
            neig.append(nei)
    for nei in neig:
        coupl[colors[ind]][nei].remove(ind)
    colors[ind] = -1
print(reach)
cumsum = [0]*(n+1)
for i in range(n):
    cumsum[i+1] = cumsum[i] + (reach[i]-i+1)
print(cumsum)

q = int(input())
for _ in range(q):
    l,r = [int(x)-1 for x in input().split()]
    if reach[l]>r:
        N = r-l+1
        print('allt funkar',l,r)
        print(N*(N+1)//2)
        break
    a = l
    b = n
    while b-a>1:
        m = (a+b)//2
        if reach[m]<=r:
            a=m
        else:
            b=m

    print('Funkar fran',l,a+1,r)
    summa = 0
    summa += cumsum[a+1] - cumsum[l]
    print('Från första får')
    if a+1<=r:
        N = r-(a+1)+1
        print('Nst pekar ut',N)
        summa += N*(N+1)//2
    print(summa)
