Problem Description

Translated from COCI 2014/2015 Contest 3 T6 "KAMIONI"

Consider a highway as a number line. There are $N$ trucks on the highway, all initially located at integer points. All trucks start moving simultaneously at the same speed, and no truck remains stationary. Each truck can move one unit distance in one minute.

Each truck is given a "route" represented by an array of $k$ elements $A_1, A_2, \dots, A_k$. The truck first travels from $A_1$ to $A_2$, then immediately turns around to travel to $A_3$, and so on. The time taken to turn around is ignored. Given the nature of the routes, we ensure:

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

An example route might be $2 \rightarrow 5 \rightarrow 1 \rightarrow 7$ (the points given are either starting points, endpoints, or turning points). Initially, the truck is at position $2$, and after 3 minutes, it reaches position $5$, turns around, and continues to position $1$, which it reaches 7 minutes after starting. The truck turns again and travels to position $7$, which it reaches 13 minutes after starting.

When a truck reaches the end of its route, mysterious aliens Planet6174 will appear and take it back to their spaceship.

Given the routes of these $N$ trucks, there are $M$ queries, each involving a pair of trucks. For each query, determine how many times the pair of trucks will be at the same position. The positions do not have to be integers; for example, they might meet at position $2.5$.

Note that for each pair of trucks in the queries:

• They will not be at the same position when one of them is taken by the aliens.
• They will not be at the same position at the initial moment or when one of them turns.

Planet6174: The translator of this problem has been dealt with (jokingly)

Input Format

The first line contains two integers $N$ and $M (1 \le N \le 10^5, 1 \le M \le 10^5)$, representing the number of trucks and the number of queries, respectively.

The next $N$ lines describe the routes of the trucks. Each line starts with an integer $K_i (1 \le K_i \le 3 \cdot 10^5)$, the length of the route, followed by $K_i$ integers $A_j (1 \le A_j \le 10^9)$, representing the points on the truck's route. The total distance traveled by all trucks combined does not exceed $3 \cdot 10^5$.

The next $M$ lines each contain two integers $(a_i, b_i)$, representing the pair of trucks for the $i$-th query.

Output Format

Output $M$ lines, where the $i$-th line contains the number of times the $i$-th queried pair of trucks meet.

Sample Input and Output

Input Sample #1

3 3
3 1 3 1
2 2 1
3 3 1 3
1 2
2 3
3 1

Output Sample #1

1
0
2

Input Sample #2

2 1
4 1 6 3 6
7 3 4 2 6 5 6 1
1 2

Output Sample #2

3

Input Sample #3

3 4
3 1 4 2
4 3 4 2 4
3 4 1 3
1 2
2 3
3 1
1 3

Output Sample #3

2
1
2
2

Notes/Hints

For 50% of the test cases, it is guaranteed that $N \le 10^2, K_i \le 10^3, M \le 10^3$.

见题面 Input 部分

见题面 Output 部分