h2. Restricţii
* $1 ≤ lifespan{~i~}$

* Suma lifespan-urilor nu va depasi $100.000$

* suma lifespan-urilor nu va depasi $100.000$

* $1 ≤ N ≤ 100.000$

* Toti timpii din datele de intrare (atat timpii calatorilor cat si timpii din query-uri) apartin intervalului $[1, 2.000.000.000]$

* toti timpii din datele de intrare (atat timpii calatorilor cat si timpii din query-uri) apartin intervalului $[1, 2.000.000.000]$

* Pentru $20%$ din teste $M = 1$
* Pentru alte $20%$ din teste, suma lifespan-urilor este mai mica ca $1000$
* Pentru alte $20%$ din teste, timpii folositi sunt pana in $100.000$

|20
1000
1001

|
|2 3
4 100 46 1000 96
2 99 1
20
50
1001
|1000
1000
1001
|

|

h3. Explicaţie

10204