Fişierul intrare/ieşire:	infinitywar.in, infinitywar.out	Sursă	RMI 2015
Autor	Catalin Francu	Adăugată de	Bogdan Ciobanu •bciobanu
Timp execuţie pe test	0.6 sec	Limită de memorie	36864 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Infinitywar

În urma evenimentelor petrecute în New York, cele N lumi ale universului Marvel se află în război. Lumea i (1 ≤ i ≤ N) este reprezentată, în acest război final, de o armată alcătuită din K_i soldaţi (posibil zero). Fiecare soldat are o singură super putere reprezentată de un număr pozitiv întreg (între 1 şi P). Puterile tuturor soldaţilor în cadrul unei armate sunt diferite.

S-a observat că, în bătălie directă, doi soldaţi se vor anihila dacă şi numai dacă cei doi au aceeaşi putere. Spre exemplu, dacă o armată formată din soldaţii cu puterile {1, 3, 5} se luptă cu armată {2, 3, 6}, atunci soldaţii care rămân în viaţă la finalul bătăliei sunt: {1, 2, 5, 6}.

Cele N lumi sunt aranjate secvenţial: prima lume are indexul 1, în timp ce ultima are indexul N.

Cerinţă

Thanos este destul că sigur că poate câştiga războiul şi distruge universul, însă doreşte să se distreze în timp ce face asta. Aşadar, el a pregătit Q întrebări. Pentru fiecare întrebare se dau doi indici x şi y şi trebuie găsit numărul de soldaţi care ar supravieţui bătăliei dintre armatele cu indicii x, x+1, x+2, ..., y.

Date de intrare

Prima linie a fişierului de input infinitywar.în conţine două numere întregi N şi Q.

Următoarele N linii conţin descrieri ale armatelor. Linia i+1 conţine un număr K_i urmat de K numere (numărul puterii fiecărui soldat).

Următoarele Q linii conţin câte două numere x şi y, separate prin câte un spaţiu.

Date de ieşire

Fişierul de ieşire infinitywar.out trebuie să conţină Q linii. Fiecare linie trebuie să conţină un singur număr, raspunul pentru întrebarea corespunzătoare.

Restricţii

• 1 ≤ N ≤ 50.000
• 1 ≤ P ≤ 10.000
• 1 ≤ Q ≤ 100.000
• K₁ + K₂ + ... + K_N ≤ 300.000
• 1 ≤ x ≤ y ≤ N pentru fiecare întrebare.
• Pentru 30% dintre teste N ≤ 10.000, P ≤ 500 şi Q ≤ 10.000
• Pentru alte 40% dintre teste P ≤ 5.000 şi Q ≤ 30.000

Exemplu

Cum se trimit solutii?