Trucks on the Road

This problem is adapted from COCI 2014/2015 Contest 3, Task KAMIONI.

There is a road which is modeled as a number line. On the road, there are N trucks which all start at integer positions. All trucks start moving simultaneously at the same constant speed of 1 unit per minute and none of them ever stops. Each truck follows a route given by an array of k integers: A₁, A₂, …, A_k. The truck starts at A₁ and drives to A₂, then immediately reverses direction and drives to A₃, and so on. The turning (reversal) is instantaneous (i.e. no time is lost during a turn). It is guaranteed that the route alternates in direction, i.e. either:

• A₁ < A₂ > A₃ < A₄ > …, or
• A₁ > A₂ < A₃ > A₄ < …

Once a truck reaches its final destination, a mysterious alien (Planet6174) appears and takes it away. You are given the routes for all N trucks. There are M queries, and each query gives a pair of trucks. For each query, determine the number of times the two trucks meet (i.e. are exactly at the same position at the same time), excluding the meeting events occurring at time 0, at any turning points, or when one of the trucks gets taken away. Note that meetings may occur at non-integer positions (e.g. 2.5).

Note: For every queried pair of trucks, it is guaranteed that when one of them is taken away by the aliens, they are not at the same position, and they never meet at the starting time or exactly at a turning point.

inputFormat

The first line contains two integers N and M (1 ≤ N, M). Then follow N descriptions of the trucks. For each truck, the first integer k (k ≥ 2) denotes the number of points in its route, followed by k integers A1, A2, …, Ak, representing the route. All trucks start moving at time 0 from A1 along the route. Then M lines follow, each containing two integers u and v (1-indexed) representing a query: count the number of meetings between truck u and truck v.

outputFormat

For each query, output a single integer on a separate line – the number of times the two trucks meet (excluding events at time 0, turning points, or when a truck is taken away).

sample

2 1
3 2 5 1
2 3 1
1 2

1