Problem Description

In Yugo, all cities are located on a straight line connected by a straight highway. There are $n$ motor vehicles moving back and forth on this highway. They can only turn around at certain cities, and this action does not take any time. The vehicles do not stop. Initially, these $n$ vehicles may be located at different cities. They all start at the same moment, and each vehicle can move to the next city every minute, i.e., it can travel a distance of $1$ unit per minute. When a vehicle reaches its destination, it will disappear. Given the movement trajectories of each vehicle, which include the starting point, each turning point, and the destination, there are $m$ queries. Each query specifies two vehicles and asks how many times they have encountered each other.

Note: The encounter point of the vehicles may not necessarily be a city. Additionally, an encounter does not count if one of the vehicles reaches its destination at the same moment; an encounter does not count if both vehicles start at the same location; an encounter does not count if one of the vehicles is just turning around.

Input Format

The first line contains two integers $n$ and $m$, representing the number of vehicles and the number of queries, respectively.

The next $n$ lines, each starting with an integer $K_i$, indicate that the vehicle's path includes $K_i$ cities. Following are $K_i$ numbers, each within the range $[1, 10^7]$, representing the cities the vehicle passes through in order, including the starting and ending points.

The sum of all $K_i$ does not exceed $3 \times 10^5$.

The next $m$ lines each contain two integers, representing the two vehicles for which the number of encounters is queried.

Output Format

For each query, output a single integer representing the number of encounters between the two specified vehicles.

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

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 #2

2
1
2
2

Notes

For $50\%$ of the data, $n < 100, K_i < 1000, m < 1000$.

For $100\%$ of the data, $2 \le K_i \le 3 \times 10^5$, $n \le 10^5, m < 10^5$.

The city numbers are within $[1, 10^9]$. Each vehicle changes direction no more than $3 \times 10^5$ times; the total number of turns for all vehicles does not exceed $3 \times 10^5$.

见题面 Input 部分

见题面 Output 部分