Cerința

RAU-Gigel și-a descoperit o nouă pasiune: graffiti-ul. El simte o nevoie din ce în ce mai puternică de a-și manifesta spiritul artistic, de a exersa, de a explora, și de a încerca noi și noi tehnici … și pentru asta are nevoie de spațiu.

Făcând o incursiune prin cartier, RAU-Gigel descoperă un depou părăsit împrejmuit de un gard format din plăci de beton de lățimi și înălțimi diferite, dispuse în linie continuă. „O pânză imaculată” se gândește el. Și începe să măsoare plăcile de beton, una câte una, cu gândul ca, odată ajuns acasă, să schițeze următoarea sa creație artistică.

El vrea să aleagă câteva plăci de beton alăturate și pe dreptunghiul maximal delimitat de acestea, să își făurească creația. Care este suprafața maximă de desenare ? Ajutați-l pe RAU-Gigel să facă mai multe simulări.

În imaginea alăturată gardul format din plăci de beton, numerotate de la 1 la 5, de dimensiuni (lățime X înălțime): 4 X 8, 5 X 4, 7 X 2, 3 X 3, 8 X 10 unități de mărime. Prin interogări repetate de forma (x, y), RAU-Gigel vrea să afle cât de mare poate fi suprafața de desenare în formă dreptunghiulară ce va acoperi plăcile de beton alipite: x, x+1, ... , y.

De exemplu, la interogarea (2, 4), desenul va avea lățimea 5 + 7 + 3 = 15, și înălțimea minim (4, 2, 3) = 2, deci suprafața de desenare va fi de mărime 30. Se va folosi peste tot aceeași unitate de mărime.

Date de intrare

Fișierul de intrare graffiti.in conține pe prima linie numărul natural N reprezentând numărul de plăci de

beton, indexate de la 1 la N, apoi N linii care conțin perechi de forma L H, separate printr-un spațiu, reprezentând lățimea și înălțimea fiecărei plăci de beton. Urmează apoi un rând cu numărul natural Q ce reprezintă numărul de interogări, urmat de Q linii ce conțin interogările: perechi de forma x y, cu x ≤ y, separate printr-un spațiu.

Date de ieșire

Fișierul de ieșire graffiti.out va conține răspunsurile la interogări, în ordinea solicitării, câte unul pe linie.

Restricții și precizări

• 1 ≤ N, Q, L, H ≤ 100.000, 1 ≤ x ≤ y ≤ N
• Pentru teste în valoare de 40 de puncte: N, Q ≤ 1.000
• Pentru alte teste în valoare de 30 de puncte: N ≤ 1.000

Exemplu:

graffiti.in

5
4 8
5 4
7 2
3 3
8 10
2
2 4
4 5

graffiti.out

30
33

Explicație

Avem 5 plăci de beton cu dimensiunile 4 X 8, 5 X 4, 7 X 2, 3 X 3, 8 X 10 și 2 interogări.

La interogarea (2, 4), suprafața desenată va avea lățimea 5 + 7 + 3 = 15, și înălțimea minim (4, 2, 3) = 2, deci suprafața 30.

La interogarea (4, 5), suprafața desenată va avea lățimea 3 + 8 = 11, iar înălțimea sa va fi 3, deci suprafața 33.