Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

LQDGRAPE - Trồng nho 2

 

Vào năm 2050, nho trở thành trái cây được ưa chuộng nhất. Rượu nho, nho tươi, nho khô, kẹo trái cây vị nho, … được tiêu thụ với số lượng cực lớn. Bởi thế ngành trồng và chế biến sản phẩm từ nho thu lãi rất cao. Tập đoàn RICH, sau khi đã thành công trong vụ đầu tư vào khu đất “vàng” ở Sài Gòn, quyết định lấn sang lĩnh vực trồng nho.Ban giám đốc RICH quyết định sẽ đầu tư thuê một khu đất lớn ở Phan Rang – vùng trồng nho tốt nhất Việt Nam. Sở dĩ phải thuê vì RICH đã bỏ nhiều tiền để mua khu đất “vàng”.
            Vùng đất nông nghiệp ở Phan Rang được chia thành các block –một khu đất hình vuông diện tích 1 hecta. Do vị trí địa lí đặc biệt (phía Đông giáp biển, phía Tây là các dãy núi)nên độ cao trung bình của các block đất ở Phan Rang có tính chất không giảm theo chiều từ Đông sang Tây và từ Bắc xuống Nam. Vùng đất nông nghiệp có thể được biểu diễn bằng một bảng H kích thước M dòng, N cột, mỗi ô biểu diễn độ cao của 1 block đất. Ô (1,N) ở phía Đông Bắc còn ô (M,1) ở phía Tây Nam. Ví dụ với M=4 và N=5 :

Vào năm 2050, nho trở thành trái cây được ưa chuộng nhất. Rượu nho, nho tươi, nho khô, kẹo trái cây vị nho, … được tiêu thụ với số lượng cực lớn. Bởi thế ngành trồng và chế biến sản phẩm từ nho thu lãi rất cao. Tập đoàn RICH, sau khi đã thành công trong vụ đầu tư vào khu đất “vàng” ở Sài Gòn, quyết định lấn sang lĩnh vực trồng nho.Ban giám đốc RICH quyết định sẽ đầu tư thuê một khu đất lớn ở Phan Rang – vùng trồng nho tốt nhất Việt Nam. Sở dĩ phải thuê vì RICH đã bỏ nhiều tiền để mua khu đất “vàng”.

Vùng đất nông nghiệp ở Phan Rang được chia thành các block –một khu đất hình vuông diện tích 1 hecta. Do vị trí địa lí đặc biệt (phía Đông giáp biển, phía Tây là các dãy núi)nên độ cao trung bình của các block đất ở Phan Rang có tính chất không giảm theo chiều từ Đông sang Tây và từ Bắc xuống Nam. Vùng đất nông nghiệp có thể được biểu diễn bằng một bảng H kích thước M dòng, N cột, mỗi ô biểu diễn độ cao của 1 block đất. Ô (1,N) ở phía Đông Bắc còn ô (M,1) ở phía Tây Nam. Ví dụ với M=4 và N=5:


34 33 25 21 13
35 35 33 21 16
50 45 33 33 16
93 83 66 51 23





RICH có Q giống nho. Giống nho i được đặc trưng bởi 2 chỉ số Li và Ri chỉ có thể được trồng trên các block đất có độ cao trung bình trong đoạn [Li,Ri]. Ban lãnh đạoRICH muốn biết với mỗi giống nho, diện tích khu đất lớn nhất có thể trồng đượclà bao nhiêu. Giả sử RICH chỉ mua một khu duy nhất và khu này là một hình vuông gồm các block đất liên tiếp, có các cạnh song song với hướng Đông-Tây và Bắc-Nam. Ví dụ : với giống nho có L=20, R=90 thì khu đất lớn nhất gồm các ô được tô đậm trên hình.

Input

 

Dòng đầu gồm 3 số nguyên dương M,N,Q ( 1 <= M,N <= 500; 1 <= Q <= 10^4)

M dòng sau, mỗi dòng N số Hij là độ cao trung bình của block đất (i,j)  ( 0 <= Hij<= 10^5)

Q dòng sau, mỗi dòng 2 số Li, Ri ( 0 <= Li<= Ri<= 10^5).

 

Output

Gồm Q dòng, dòng thứ i gồm 1 số nguyên duy nhất là diện tích khu đất lớn nhất có thể trồng giống nho i. Nếu không tồn tại khu đất nào thỏa thì coi như diện tích bằng 0.

Example

Input:
4 5 3
17 18 22 26 18
26 16 26 13 19
20 11 13 09 27
01 29 08 11 14
1 16
8 29
12 18

Output:
4
16
1
Input:
4 5 3
34 33 25 21 13
35 35 33 21 16
50 45 33 33 16
93 83 66 51 23
22 90
33 35
20 100

Output:
9
4
16

Mọi thắc mắc về bộ test xin liên hệ white_cobra

Note: Máy chấm mới khá mạnh , có thể mạnh hơn máy ở nhà bạn nên có thể ở máy của bạn chạy khá lâu nhưng submit lại AC


Được gửi lên bởi:Tmbao
Ngày:2013-01-01
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:Hiểu sai đề bài GRAPE

hide comments
2015-08-29 15:39:28 Anh Duc Le
Cả bài này lần bài GRAPE đều được set time limit rất chặt :|
2013-06-12 14:05:18 vn_army
máy chấm mới dị thật
core i5 ivy ở nhà chạy test max còn hơn 4s ...
lần đầu đọc cũng bị nhầm y hệt thế này , code gần xong mới phát hiện cái đoạn gạch kia =))
2013-01-06 14:43:54 Noyethug
đây không phải do hiểu sai để mà là do đọc không kĩ đề :P
mình còn tưởng hiểu sai là hiểu sai từ "trung bình" (tổng các ô chia diện tích) chứ
2013-01-02 14:48:31 .
may cham manh that!!!!
2013-01-02 09:46:44 Tmbao
Bộ test sai nên đã được sửa, các bài kết quả sai đã được rejudge và thành chạy quá lâu .

Last edit: 2013-01-02 09:47:17
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.