Graffiti

Cerință

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 $min(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 \leq 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 \leq N, Q, L, H \leq 100 \ 000$, $1 \leq x \leq y \leq N$;
• Pentru teste în valoare de $40$ de puncte: $N, Q \leq 1 \ 000$;
• Pentru alte teste în valoare de $30$ de puncte: $N \leq 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 $min(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$.