Infinity War

Î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, \dots, y$.

Date de intrare

Prima linie a fişierului de input infinitywar.in 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_i$ 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 și precizări

• $1 \leq N \leq 50 \ 000$
• $1 \leq P \leq 10 \ 000$
• $1 \leq Q \leq 100 \ 000$
• $K_1 + K_2 + \dots + K_N \leq 300 \ 000$
• $1 \leq x \leq y \leq 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

infinitywar.in

4 3
2 1 2
3 1 3 97
2 1 341
5 4 2 981 341 97
1 3
2 4
1 4

infinitywar.out

5
4
4