탈출 경로 2

IOI 왕국에는 서쪽에서 동쪽으로 한 줄로 늘어선 $N$개의 도시가 있다. 도시에는 서쪽부터 차례로 1번부터 $N$번까지 번호가 붙어 있다.

IOI 왕국은 시간의 단위로 바이오우(Byou)를 쓴다. 하루는 $T$바이오우로 나뉜다. 하루의 시작으로부터 $x$바이오우($0 \le x < T$) 뒤의 시각을 시각 $x$라고 한다. 따라서 어떤 날의 시각 $T-1$에서 1바이오우가 지나면 다음 날의 시각 $0$이 된다.

JOI 그룹은 IOI 왕국의 비밀 결사이다. 구성원은 나라 곳곳의 검문소를 피해 다녀야 하므로, 도시 간 이동에는 JOY 항공사가 운항하는 항공편만 이용한다.

JOY 항공사는 도시 $i$($1 \le i \le N-1$)에서 출발하는 항공편을 $M_i$개 운항한다. $j$번째 항공편($1 \le j \le M_i$)은 매일 시각 $A_{i,j}$에 도시 $i$에서 출발하여 같은 날 시각 $B_{i,j}$에 도시 $i+1$에 도착한다. 여기서 $A_{i,j} < B_{i,j}$이다. 이 항공편들로 편리하게 환승할 수 있다. 도착하자마자 바로 출발할 수도 있고, 항공사의 공항에서 하룻밤 머물 수도 있다.

JOI 그룹에는 1번부터 $Q$번까지 번호가 붙은 구성원 $Q$명이 있다. 구성원 $k$($1 \le k \le Q$)의 작전 기지는 도시 $L_k$에, 생활 기지는 도시 $R_k$에 있다. 각 구성원은 도시 $L_k$에서 출발하는 시각과 이용할 항공편을 골라 $L_k$에서 $R_k$까지 가는 데 걸리는 최소 시간을 알고 싶어 한다.

주어진 항공편 정보와 구성원의 기지 정보를 바탕으로, 각 구성원 $k$가 도시 $L_k$에서 도시 $R_k$까지 가는 데 필요한 최소 시간을 구하는 프로그램을 작성하라.

표준 입력에서 다음 데이터를 읽는다.

N T
M_1
A_{1,1} B_{1,1}
A_{1,2} B_{1,2}
...
A_{1,M_1} B_{1,M_1}
M_2
...
M_{N-1}
...
Q
L_1 R_1
L_2 R_2
...
L_Q R_Q

표준 출력에 $Q$개의 줄을 출력한다. $k$번째 줄에는 구성원 $k$가 도시 $L_k$에서 도시 $R_k$까지 가는 데 필요한 최소 시간을 출력한다.

• $2 \le N \le 100\,000$.
• $2 \le T \le 10^9$.
• $M_i \ge 1$ ($1 \le i \le N-1$).
• $M_1 + M_2 + \cdots + M_{N-1} \le 100\,000$.
• $0 \le A_{i,j} < B_{i,j} < T$ ($1 \le i \le N-1$, $1 \le j \le M_i$).
• $1 \le Q \le 300\,000$.
• $1 \le L_k < R_k \le N$ ($1 \le k \le Q$).
• 입력되는 값은 모두 정수이다.