Giải bài trực tuyến

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:

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