Dãy núi JOI gồm nhiều ngọn núi, được biểu diễn bằng một lưới có \(H\) hàng và \(W\) cột. Chiều dọc của lưới là hướng Bắc–Nam, còn chiều ngang là hướng Đông–Tây. Ô ở hàng thứ \(i\) tính từ phía Bắc (\(1 \le i \le H\)), cột thứ \(j\) tính từ phía Tây (\(1 \le j \le W\)) được ký hiệu là \((i,j)\). Mỗi ô có đúng một ngọn núi. Độ cao đỉnh núi tại ô \((i,j)\) là \(T_{i,j}\).

Bitaro là một chú hải ly có sức bật \(L\). Khi đang đứng trên một đỉnh núi, Bitaro có thể di chuyển bằng một cú nhảy cao, gồm các bước sau theo thứ tự:

1. Bitaro bay thẳng lên từ đỉnh núi hiện tại. Nếu đỉnh núi có độ cao \(x\), Bitaro sẽ lơ lửng ở độ cao \(x+L+0.5\).
2. Bitaro di chuyển sang một ô kề theo một trong bốn hướng Đông, Tây, Nam, Bắc mà không thay đổi độ cao, lặp lại việc này không hoặc nhiều lần. Tại mọi ô đi qua, đỉnh núi phải thấp hơn độ cao mà Bitaro đang lơ lửng.
3. Bitaro hạ xuống đỉnh núi ở ô hiện tại.

Bitaro đang lên kế hoạch cho \(Q\) chuyến đi. Trong chuyến đi thứ \(k\) (\(1 \le k \le Q\)), Bitaro muốn đi từ đỉnh núi tại ô \((A_k,B_k)\) đến đỉnh núi tại ô \((C_k,D_k)\) chỉ bằng các cú nhảy cao. Bitaro muốn biết từng chuyến đi có thực hiện được hay không. Vì mỗi lần bay lên tiêu tốn nhiều sức lực, nếu thực hiện được, Bitaro còn muốn biết số cú nhảy cao ít nhất cần dùng.

Cho thông tin về các ngọn núi, sức bật của Bitaro và các kế hoạch di chuyển. Với mỗi chuyến đi, hãy xác định có thể thực hiện được hay không và, nếu có, tìm số cú nhảy cao ít nhất cần dùng.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn:

• Dòng thứ nhất chứa ba số nguyên \(H,W,L\).
• Trong \(H\) dòng tiếp theo, dòng thứ \(i\) chứa \(W\) số nguyên \(T_{i,1},T_{i,2},\ldots,T_{i,W}\).
• Dòng tiếp theo chứa số nguyên \(Q\).
• Trong \(Q\) dòng tiếp theo, dòng thứ \(k\) chứa bốn số nguyên \(A_k,B_k,C_k,D_k\).

Các số trên cùng một dòng được ngăn cách bởi dấu cách.

Dữ liệu ra

In ra đầu ra chuẩn \(Q\) dòng. Dòng thứ \(k\) (\(1 \le k \le Q\)) chứa số cú nhảy cao ít nhất cần dùng cho chuyến đi thứ \(k\) nếu có thể thực hiện chuyến đi đó; nếu không, in ra -1.

Ràng buộc

• \(1 \le H\).
• \(1 \le W\).
• \(2 \le H \times W \le 300000\).
• \(1 \le L \le 10^9\).
• \(1 \le T_{i,j} \le 10^9\) với \(1 \le i \le H\), \(1 \le j \le W\).
• \(1 \le Q \le 300000\).
• \(1 \le A_k \le H\) và \(1 \le C_k \le H\) với \(1 \le k \le Q\).
• \(1 \le B_k \le W\) và \(1 \le D_k \le W\) với \(1 \le k \le Q\).
• \((A_k,B_k) \ne (C_k,D_k)\) với \(1 \le k \le Q\).
• Tất cả các giá trị trong dữ liệu vào đều là số nguyên.

Chấm điểm

1. \(10\) điểm: \(H \times W \le 300\), \(Q \le 150000\).
2. \(20\) điểm: \(H \times W \le 3000\), \(Q \le 150000\).
3. \(20\) điểm: \(H \times W \le 150000\), \(Q \le 150000\), \((A_k,B_k)=(1,1)\) với mọi \(1 \le k \le Q\).
4. \(30\) điểm: \(H \times W \le 150000\), \(Q \le 150000\).
5. \(20\) điểm: Không có ràng buộc bổ sung.

Ví dụ

2 4 5
1 3 22 1
8 13 6 16
6
1 1 2 2
1 1 1 3
1 1 2 3
1 1 2 4
1 1 1 4
1 1 1 2

3
-1
3
4
4
1

6 5 11
175 100 110 117 158
144 133 123 150 191
167 252 219 181 346
231 241 280 201 209
261 332 325 225 338
269 298 315 291 308
12
1 1 4 2
1 1 1 5
1 1 5 1
1 1 5 4
1 1 3 4
1 1 6 4
1 1 2 5
1 1 3 1
1 1 4 4
1 1 5 5
1 1 6 2
1 1 6 1

8
1
10
6
1
13
2
1
3
19
14
11

4 4 5
53 55 51 49
56 60 89 45
54 57 92 43
96 99 95 92
9
1 4 2 3
4 1 3 2
2 4 2 3
2 1 4 1
1 2 1 1
2 4 1 1
4 1 2 3
3 4 1 1
1 3 1 4

-1
1
-1
-1
1
3
1
4
1

Giới hạn

Giới hạn thời gian là \(4\) giây; giới hạn bộ nhớ là \(1024\) MB.

Nguồn

Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.

Bản dịch tiếng Việt từ đề tiếng Anh và tiếng Nhật của Ủy ban Olympic Tin học Nhật Bản, JOI 2024/2025, vòng tuyển chọn mùa xuân, ngày thi thứ nhất. Tham khảo thêm thông báo triển khai và thông tin chấm điểm.