Shortest Flight Time

The IOI Kingdom consists of N cities arranged from west to east and numbered from \(1\) to \(N\). A day in the kingdom is divided into \(T\) time units (called Byous). The time units are numbered from \(0\) to \(T-1\); after time \(T-1\) comes time \(0\) of the next day.

The JOI organization, which needs to avoid the national checkpoints, can only travel using flights operated by JOY Airlines. In city \(i\) (for \(1 \le i \le N-1\)), JOY Airlines operates \(M_i\) flights. The \(j\)th flight (\(1 \le j \le M_i\)) departs daily from city \(i\) at time \(A_{i,j}\) and arrives at city \(i+1\) at time \(B_{i,j}\) (with \(A_{i,j} < B_{i,j}\)). Note that immediate transfers are allowed, and one may wait overnight at an airport.

There are \(Q\) members of the JOI organization. The \(k\)th member has set city \(L_k\) as his operational base and city \(R_k\) as his residential base. Each member wants to know the minimum time needed to travel from city \(L_k\) to city \(R_k\) by choosing an appropriate departure time (i.e. they can start at any time of their choice) and a sequence of flights.

Your task is to compute, for each member \(k\), the shortest travel time from city \(L_k\) to city \(R_k\). If \(L_k = R_k\), then the answer is \(0\).

Transition detail: Suppose you are at a city at time \(x\) (\(0 \le x A, \end{cases} \] and the total time using that flight will be \[ \text{wait} + (B - A) + \text{(additional time from arrival time } B\text{)}. \]

inputFormat

The input begins with a line containing two integers \(N\) and \(T\). Then for each city \(i\) from \(1\) to \(N-1\):

M_i
A_{i,1} B_{i,1}
A_{i,2} B_{i,2}
...
A_{i,M_i} B_{i,M_i}

Then a line with an integer \(Q\) is given, followed by \(Q\) lines each containing two integers \(L_k\) and \(R_k\) (\(1 \le L_k, R_k \le N\)).

outputFormat

For each query, output the minimum travel time required to go from city \(L_k\) to city \(R_k\) on a separate line. If \(L_k = R_k\), output 0.

sample

3 10
2
1 3
5 7
1
2 4
2
1 3
2 3

9
2