Infinity War

After the events that took place in New York, the $N$ worlds from the Marvel Universe are at war. The world $i \ (1 ≤ i ≤ N)$ is represented, in this final war, by an army consisting of $K_i$ soldiers (possibly zero). Each soldier has a single super power represented by a positive integer (between $1$ and $P$). The powers of all the soldiers in an army are different.

It has been observed that, in direct battle, two soldiers annihilate each other if and only if they have the same power. For example, if an army consisting of soldiers with powers $\{1, 3, 5\}$ battles an army $\{2, 3, 6\}$, the following soldiers remain alive at the end of the battle: $\{1, 2, 5, 6\}$.

The $N$ worlds are arranged sequentially. The first world has index $1$ and the last world has index $N$.

Task

Thanos is pretty sure that he can win the war and destroy the universe, but he also wants to have fun while doing it. He has prepared $Q$ questions for you. For each question you are given two indexes $x$ and $y$ and you have to find the number of soldiers that would survive a battle between the armies with indexes $x, x + 1, \dots, y$.

Input

The first line of the input file infinitywar.in contains two numbers $N$ and $Q$.

The next $N$ lines contain the descriptions of the armies. Line $i+1$ (where $1 ≤ i ≤ N$) contains a number $K_i$ (number of soldiers) followed by $K_i$ numbers (power number of each soldier).

The next $Q$ lines each contain two numbers $x$ and $y$ separated by a space.

Output

The output file infinitywar.out must contain $Q$ lines. Each line must contain a single number, the answer to the corresponding question.

Constraints and notes

• $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$ for every question.
• For $30\%$ of tests: $N ≤ 10 \ 000, P ≤ 500$ şi $Q ≤ 10 \ 000$
• For another $40\%$ of tests: $P ≤ 5 \ 000$ şi $Q ≤ 30 \ 000$

Example

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