Vương quốc IOI gồm \(N\) thành phố nằm trên một đường từ tây sang đông, được đánh số từ \(1\) đến \(N\) theo thứ tự từ phía tây.

Ở vương quốc IOI, đơn vị thời gian là Byou và một ngày dài \(T\) Byou. Thời điểm đã trôi qua \(x\) Byou kể từ đầu ngày, với \(0 \le x < T\), được gọi là thời điểm \(x\). Vì vậy, sau một Byou kể từ thời điểm \(T-1\) của một ngày là thời điểm \(0\) của ngày tiếp theo.

JOI là một tổ chức bí mật hoạt động trong vương quốc IOI. Các thành viên phải tránh những trạm kiểm soát của vương quốc, nên khi di chuyển giữa các thành phố, họ chỉ được sử dụng các chuyến bay của hãng hàng không JOY.

Hãng JOY khai thác \(M_i\) chuyến bay khởi hành từ thành phố \(i\) \((1 \le i \le N-1)\). Chuyến bay thứ \(j\) \((1 \le j \le M_i)\) khởi hành từ thành phố \(i\) vào thời điểm \(A_{i,j}\) mỗi ngày và đến thành phố \(i+1\) vào thời điểm \(B_{i,j}\) trong cùng ngày, với \(A_{i,j}<B_{i,j}\). Việc nối chuyến rất thuận tiện: một người có thể khởi hành đúng lúc vừa đến một thành phố. Người đó cũng có thể chờ qua đêm tại sân bay của bất kỳ thành phố nào.

Tổ chức có \(Q\) thành viên, được đánh số từ \(1\) đến \(Q\). Thành viên \(k\) có căn cứ hoạt động ở thành phố \(L_k\) và nơi sinh sống ở thành phố \(R_k\). Người đó muốn biết thời gian ngắn nhất tính từ lúc rời thành phố \(L_k\) đến lúc tới thành phố \(R_k\), khi được tự chọn thời điểm khởi hành và các chuyến bay sẽ sử dụng.

Cho thông tin về các chuyến bay và các thành viên, hãy tính thời gian ngắn nhất cho từng thành viên.

Dữ liệu vào

Đọc từ đầu vào chuẩn theo định dạng:

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

Dữ liệu ra

In \(Q\) dòng. Dòng thứ \(k\) chứa thời gian ngắn nhất để thành viên \(k\) đi từ thành phố \(L_k\) đến thành phố \(R_k\), tính bằng Byou nhưng không in tên đơn vị.

Ràng buộc

• \(2 \le N \le 100\,000\).
• \(2 \le T \le 10^9\).
• \(M_i \ge 1\) với mọi \(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\) với mọi \(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\) với mọi \(1 \le k \le Q\).
• Tất cả giá trị đầu vào đều là số nguyên.

Phân nhóm

• Nhóm 1 (6 điểm): \(N \le 2\,000\) và \(M_i=1\) với mọi \(i\).
• Nhóm 2 (8 điểm): \(N \le 2\,000\) và \(M_i \le 5\) với mọi \(i\).
• Nhóm 3 (17 điểm): \(M_i=1\) với mọi \(i\).
• Nhóm 4 (23 điểm): \(M_i \le 5\) với mọi \(i\).
• Nhóm 5 (36 điểm): \(N \le 90\,000\), \(Q \le 90\,000\) và \(M_1+\cdots+M_{N-1} \le 90\,000\).
• Nhóm 6 (10 điểm): Không có ràng buộc bổ sung.

Ví dụ

4 10000
1
100 300
2
200 400
300 600
1
500 600
3
1 3
2 4
1 4

500
400
10500

6 10000
1
100 300
1
400 700
1
500 600
1
300 900
1
200 800
1
1 6

30700

Nguồn

JOI 2023/2024, kỳ thi tuyển chọn mùa xuân, ngày thi thứ tư (24/03/2024). Đề của Ủy ban Olympic Tin học Nhật Bản (JCIOI). Bản dịch tiếng Việt theo giấy phép CC BY-SA 4.0.