Truck Encounters

We watch $N$ trucks move along a road. The road is a number line, and every integer point on it holds one city. A city is named by the coordinate of the point it sits on.

All trucks move at the same speed, and no truck stands still at any moment. A truck covers the distance between two adjacent cities in 1 minute.

The route of every truck is given. All trucks start their routes at the same moment.

A route is an array of $k$ cities $A_1, A_2, \dots, A_k$. The truck starts at city $A_1$ and drives to city $A_2$, then turns and drives to city $A_3$, and so on to the end of the route. Because the truck turns every time, one of the following holds.

$A_1 < A_2 > A_3 < A_4 > \dots \qquad \text{or} \qquad A_1 > A_2 < A_3 > A_4 < \dots$

Turning takes no time.

For example, take the route 2, 5, 1, 7. The truck is at city 2 at the start and reaches city 5 three minutes after departure. It turns there and drives to city 1, where it arrives 7 minutes after departure. It turns again and drives to city 7, reaching it at minute 13.

A truck that has driven its whole route is taken away by aliens in their space rocket, so it disappears from the road.

For some pairs of trucks we want to know how many times the two trucks met on the road, that is, how many times they were at the same position. The position where they meet does not have to be an integer. They may meet at position 2.5.

Given the number of trucks $N$, the route of each truck, and $M$ pairs of trucks, write a program that computes the number of encounters of each pair.

Every queried pair $(a_i, b_i)$ satisfies both of these conditions.

• The two trucks are not at the same position at the moment when one of them (or both) disappears from the road.
• The two trucks are not at the same position at the starting moment, nor at a moment when one of them (or both) turns.

These conditions hold only for the queried pairs, not for every pair of trucks.

The first line contains the number of trucks $N$ and the number of queried pairs $M$ ($1 \le N \le 10^5$, $1 \le M \le 10^5$).

The $i$-th of the next $N$ lines describes the route of the $i$-th truck. The first integer on the line is the number of cities on the route, $K_i$ ($2 \le K_i \le 3 \times 10^5$), followed by $K_i$ city numbers $A_j$ ($1 \le A_j \le 10^9$) in the order the truck visits them.

The sum of the route lengths over all trucks does not exceed $3 \times 10^5$.

Each of the next $M$ lines contains two integers $a_i$ and $b_i$, the numbers of the two trucks whose encounter count is asked for.

Output $M$ lines. The $i$-th line contains the number of encounters of the $i$-th pair of trucks from the input.