== include(page="template/taskheader" task_id="infinitywar") ==
Poveste şi cerinţă...
Î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$.
!>problema/infinitywar?marvel.png!
h2. 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$.
h2. Date de intrare
Fişierul de intrare $infinitywar.in$ ...
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.
h2. Date de ieşire
În fişierul de ieşire $infinitywar.out$ ...
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.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 50.000$
* $1 ≤ P ≤ 10.000$
* $1 ≤ Q ≤ 100.000$
* $K{~1~} + K{~2~} + ... + 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$
h2. Exemplu
table(example). |_. infinitywar.in |_. infinitywar.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|4 3
2 1 2
3 1 3 97
2 1 341
5 4 2 981 341 97
1 3
2 4
1 4
|5
4
4
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="infinitywar") ==
