== include(page="template/taskheader" task_id="ttg") ==

Se spune ca timpul este infinit. Din fericire, Walman a hotarat ca timpul sa inceapa din anul $1$. Astfel, fie axa infinita a timpului care porneste de la timpul numerotat cu $1$. Se stie ca in fiecare an apare o barfa noua (barfa este creeata de Walman). Conform logicii, toate barfele sunt pasate mai departe in timp: la timpul $i$ se cunosc toate barfele de la $1$ la $i$, dar nu se cunosc barfe din viitor (este cunoscut trecutul, dar nu si viitorul). Cu toate acestea, Brigada de Smecherie s-a hotarat sa se opuna logicii timpului, devenind calatori in timp. Brigada de Smecherie are $M$ calatori ai timpului, iar pentru fiecare calator se stie lifespam-ul acestuia (cat traieste), cat si in ce ani isi traieste viata. Astfel, un reprezentant poate calatori din viitor in trecut, toate barfele descoperite in viitor devenind publice in prezent (daca un calator vine din viitor la timpul $i$, oficial de la timpul $i$ se cunosc nu doar barfele de la $1$ la $i$, cat si alte barfe din viitor, in functie de cantitatea de informatie detinuta de respectivul calator). Dandu-se $M$ numarul de calatori, lifespam-ul fiecaruia si anii prin care calatoresc, sa se raspunda la $N$ query-uri de tipul $time$: cate barfe se cunosc la timpul $time$.

Se spune ca timpul este infinit. Din fericire, Walman a hotarat ca timpul sa inceapa din anul $1$. Astfel, fie axa infinita a timpului care porneste de la timpul numerotat cu $1$. Se stie ca in fiecare an apare o barfa noua (barfa este creeata de Walman). Conform logicii, toate barfele sunt pasate mai departe in timp: la timpul $i$ se cunosc toate barfele de la $1$ la $i$, dar nu se cunosc barfe din viitor (este cunoscut trecutul, dar nu si viitorul). Cu toate acestea, Brigada de Smecherie s-a hotarat sa se opuna logicii timpului, devenind calatori in timp. Brigada de Smecherie are $M$ calatori ai timpului, iar pentru fiecare calator se stie lifespan-ul acestuia (cat traieste), cat si in ce ani isi traieste viata. Astfel, un reprezentant poate calatori din viitor in trecut, toate barfele descoperite in viitor devenind publice in prezent (daca un calator vine din viitor la timpul $i$, oficial de la timpul $i$ se cunosc nu doar barfele de la $1$ la $i$, cat si alte barfe din viitor, in functie de cantitatea de informatie detinuta de respectivul calator). Dandu-se $M$ numarul de calatori, lifespan-ul fiecaruia si anii prin care calatoresc, sa se raspunda la $N$ query-uri de tipul $time$: cate barfe se cunosc la timpul $time$.

h2. Date de intrare

Fişierul de intrare $ttg.in$ va contine pe prima linie $2$ numere $M$ si $N$. Pe urmatoarele $M$ linii se vor citi: $lifespam{~i~}$ (cat traieste calatorul $i$), urmat de $lifespam{~i~}$ valori reprezentand anii in care traieste acesta (fix in ordinea data). Urmatoarele $N$ linii vor contine cate un numar $time$, reprezentand cele $N$ query-uri.

Fişierul de intrare $ttg.in$ va contine pe prima linie $2$ numere $M$ si $N$. Pe urmatoarele $M$ linii se vor citi: $lifespan{~i~}$ (cat traieste calatorul $i$), urmat de $lifespan{~i~}$ valori reprezentand anii in care traieste acesta (fix in ordinea data). Urmatoarele $N$ linii vor contine cate un numar $time$, reprezentand cele $N$ query-uri.

h2. Date de ieşire

h2. Restricţii

* $1 ≤ lifespam{~i~}$
* suma lifespam-urilor nu va depasi $100.000$

* $1 ≤ lifespan{~i~}$
* 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]$
* 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$
* Pentru alte $20%$ din teste, $N ≤ 1000$

h2. Exemplu
table(example). |_. ttg.in |_. ttg.out |

|2 3
2 100 46
2 1000 96

|1 3
4 100 46 1000 96

20
50
1001
|20
1000
1001

|

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

h3. Explicaţie

...

Avem un singur calator. Aceste isi incepe viata in anul $100$ (automat afla toate barfele de la $1$ la $100$). Dupa, acesta calatoreste in anul $46$ (deci in anul $46$ se afla toate barfele din intervalul [1,100]). Atentie: din moment ce istoria se paseaza, toti anii din intervalul [46,100] or sa cunoasca la randul lor barfele [1,100]. In pasul $3$, calatorul merge la timpul $1000$ unde afla barfele [1,1000]. In ultima instanta, ajungem in anul $96$, an in care sunt varsate toate barfele de la $1$ la $1000$. Observam ca din moment ce informatia se paseaza in timp, daca in anul $96$ avem barfele de la $1$ la $1000$, atunci si in anul $100$ o sa avem acces la aceste barfe. Ca urmare, calatorul nostru cand a pornit initial din anul $100$, acesta stia atat barfele [1,100] cat si cele de la $101$ la $1000$. Automat realizam faptul ca la timpul $46$ se cunosc deasemenea toate barfele de la $1$ la $1000$. Raspunsul celor $3$ query-uri reies in urma analizelor facute.

== include(page="template/taskfooter" task_id="ttg") ==

10204