트럭 마주치기

도로를 달리는 트럭 $N$대의 움직임을 관찰한다. 도로는 수직선이고, 수직선 위의 정수 좌표마다 도시가 하나씩 있다. 도시의 이름은 그 도시가 놓인 좌표의 값과 같다.

모든 트럭은 속력이 같고, 어느 순간에도 멈춰 있는 트럭은 없다. 트럭은 인접한 두 도시 사이의 거리를 1분에 지난다.

트럭마다 경로가 주어진다. 모든 트럭은 같은 순간에 경로를 출발한다.

경로는 도시 $k$개를 늘어놓은 $A_1, A_2, \dots, A_k$로 주어진다. 트럭은 도시 $A_1$에서 출발해 도시 $A_2$까지 달리고, 방향을 바꿔 도시 $A_3$까지 달리고, 이런 식으로 경로를 끝까지 달린다. 트럭이 매번 방향을 바꾸므로 다음 중 하나가 성립한다.

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

방향을 바꾸는 데 걸리는 시간은 없다고 본다.

예를 들어 경로가 2, 5, 1, 7이라면 트럭은 처음에 도시 2에 있고, 출발한 지 3분 뒤에 도시 5에 도착한다. 여기서 방향을 바꿔 도시 1로 달려가 출발한 지 7분 뒤에 도착한다. 다시 방향을 바꿔 도시 7로 달려가 13분에 도착한다.

경로를 모두 달린 트럭은 외계인이 우주선으로 데려가므로 도로에서 사라진다.

트럭 몇 쌍을 정해서 두 트럭이 도로에서 몇 번 마주쳤는지 알고 싶다. 다시 말해 두 트럭이 같은 위치에 있던 횟수를 알고 싶다. 마주친 위치가 정수일 필요는 없다. 위치 2.5에서 마주쳐도 된다.

트럭의 수 $N$과 각 트럭의 경로, 그리고 트럭 $M$쌍이 주어질 때 각 쌍이 마주친 횟수를 구하는 프로그램을 작성한다.

질문으로 주어지는 각 쌍 $(a_i, b_i)$는 다음 두 조건을 만족한다.

• 두 트럭 중 하나가 (또는 둘 다) 도로에서 사라지는 순간에 두 트럭은 같은 위치에 있지 않다.
• 출발하는 순간, 그리고 두 트럭 중 하나가 (또는 둘 다) 방향을 바꾸는 순간에 두 트럭은 같은 위치에 있지 않다.

이 조건은 질문으로 주어지는 쌍에만 성립하고, 모든 트럭 쌍에 성립하지는 않는다.

첫째 줄에 트럭의 수 $N$과 질문할 쌍의 수 $M$이 주어진다. ($1 \le N \le 10^5$, $1 \le M \le 10^5$)

다음 $N$개 줄 중 $i$번째 줄에는 $i$번 트럭의 경로가 주어진다. 줄의 첫 정수는 경로에 있는 도시의 수 $K_i$이고 ($2 \le K_i \le 3 \times 10^5$), 그 뒤에 트럭이 지나는 순서대로 도시의 번호 $A_j$가 $K_i$개 주어진다. ($1 \le A_j \le 10^9$)

모든 트럭의 경로 길이를 더한 값은 $3 \times 10^5$을 넘지 않는다.

다음 $M$개 줄에는 각각 두 정수 $a_i$와 $b_i$가 주어진다. 마주친 횟수를 알고 싶은 두 트럭의 번호다.

$M$개 줄을 출력한다. $i$번째 줄에는 입력에서 $i$번째로 주어진 쌍의 두 트럭이 마주친 횟수를 출력한다.