Obeleži sve kategorije koje odgovaraju problemu

Godina je 3018. Takmičenja iz programiranja u Srbiji su nikad veća, imamo stotine hiljada takmičara, i stotine hiljada rundi kvalifikacija, a takmičari još uvek prepisuju jedni od drugih, i ne poštuju pravilnik.

Komisija je spremna kao i uvek, i unajmila je stotine hiljada članova koji će nadgledati prepisivanje. Svaki član Komisije ima zaduženu rundu od koje će početi nadgledanje, i normu koju treba da ispuni - tj. broj različitih takmičara koje treba da uhvati u prepisivanju. Član komisije vrši nadgledanje u svim rundama počev od zadate početne runde, dok god ne ispuni zadatu normu.

Za svakog takmičara su date runde u kojima je prekršio pravilnik, a vas molimo da pomognete Komisiji i za svakog člana odgovorite koliko najmanje rundi zaredom treba da posmatra da bi ispunio normu (norma će uvek biti takva da se može ispuniti).

Svaki član komisije će uhvatiti sve takmičare koji su prepisivali u rundi koju nadgleda. Takođe, više članova komisije mogu uhvatiti istog takmičara u istoj rundi.

Komisija je odlučila i da vam oteža posao tako što će vam informaciju o zaduženju svakog člana dati u zavisnosti od rešenja (minimalnog broja posmatranih rundi) za prethodnog člana - obratite pažnju na opis ulaza i pojašnjenja primera u ovom zadatku.

Opis ulaza

U prvoj liniji standardnog ulaza nalaze se dva broja $N$ i $R$ odvojena razmakom - broj takmičara i broj rundi kvalifikacija. U svakoj od sledećih $N$ linija se nalazi prvo broj $P_i$ - broj rundi u kojima je $i$-ti takmičar prepisivao, pa zatim $P_i$ različitih brojeva odvojenih razmakom koji označavaju runde u kojima je $i$-ti takmičar prepisivao. Zatim, u sledećem redu se nalazi broj $K$ - broj unajmljenih članova komisije. U sledećih $K$ redova se nalaze po dva broja odvojena razmakom - $T_i$ i $S_i$ koji označavaju zaduženje $i$-tog člana komisije na sledeći način: Ako je $MP_i$ minimalan broj rundi koji $i$-ti član komisije treba da posmatra, onda će $Start_i = T_i + MP_{i-1}$ biti runda u kojoj $i$-ti član treba započeti nadgledanje. $S_i$ označava normu $i$-tog člana. Uzima se da je $MP_0 = 0$, dok indeksiranje za članove komisije počinje od 1. Obratite pažnju da $T_i$ može biti i negativan broj, ali će dobijeni $Start_i$ uvek biti od $1$ do $R$.

Opis izlaza

Na standardni izlaz ispisati $K$ linija - u svakoj liniji redom brojeve $MP_i$ - koji označavaju minimalan broj rundi koje $i$-ti član komisije treba da posmatra.

Primer 1

Ulaz

6 12
3 1 2 5
2 3 4
3 1 2 7
2 3 6
0
3 3 11 12
3
1 2
0 5
1 5

Izlaz

1
3
8

Prvi član komisije započinje nadgledanje od prve runde, treba da ispuni normu 2, i odmah u prvoj rundi hvata dva takmičara (1. i 3.), što znači da nadgleda samo 1 rundu. Drugi član komisije počinje nadgledanje takođe od prve runde $(Start_2 = T_2 + MP_1 \implies Start_2 = 0 + 1 = 1)$, i potrebno je da uhvati 5 takmičara u prepisivanju. Za to je dovoljno da nadgleda 3 runde (takmičari 1 i 3 prepisuju u prvoj, dok takmičari 2, 4 i 6 prepisuju u trećoj rundi). Treći član komisije započinje nadgledanje od četvrte runde, i potrebno je da uhvati 5 takmičara u prepisivanju. Za to je potrebno da nadgleda sve runde do jedanaeste.

Primer 2

Ulaz

5 5
1 2
1 3
1 4
1 5
2 1 2
3
1 5
-2 3
-1 2

Izlaz

5
3
1

Obratite pažnju da $T_i$ može biti negativan broj na ulazu, ali uzimajući u obzir rešenja za prethodne članove komisije, drugi član komisije će nadgledanje početi od 3. runde, dok će treći član komisije nadgledanje započeti od 2. runde.

Ograničenja

• $1 \leq N,R,K \leq 300 000$
• $1 \leq \sum_{i=1}^n P_i \leq 300 000$

Test primeri su podeljeni u četiri disjunktne grupe:

• U test primerima koji vrede $25$ poena važi $1 \leq N,R,K,\sum_{i=1}^n P_i \leq 10^4$
• U test primerima koji vrede $25$ poena važi $1 \leq N,R,K,\sum_{i=1}^n P_i \leq 10^5$
• U test primerima koji vrede $25$ poena važi $S_i = S_j, \forall(i,j | 1 \leq i,j \leq K)$, tj. svi članovi komisije imaju istu normu
• U test primerima koji vrede $25$ poena nema dodatnih ograničenja