DỤNG CỤ SAN BẰNG

Nguồn: https://www.codechef.com

Nam tạo bản đồ cho một trò chơi chiến thuật thời gian thực. Trong trò chơi này, bản đồ là một hình chữ nhật 2D với kích thước là ​N× M ô. Ban đầu, ô ở hàng ​i cột ​j có độ cao là ​H​_i,j. Độ cao luôn là số nguyên.

Trước khi tạo bản đồ, Nam muốn tất cả các ô có chiều cao như nhau. Nhưng anh ta chỉ có thể thay đổi chiều cao bằng cách dùng dụng cụ ​san bằng​. Dụng cụ san bằng có dạng hình chữ nhật với kích thước ​X × Y​, và khi sử dụng, nó thay thế chiều cao của tất cả những ô bị ảnh hưởng thành ​phần tử trung vị​. Ví dụ lưới ​5× 9​ có chiều cao:

9 8 8 8 7 7 7 8 7

1 1 1 4 4 5 2 4 4

2 3 1 2 1 2 1 1 9

3 2 8 8 9 9 7 7 7

7 7 7 7 7 7 8 8 8

Giả sử dụng cụ san bằng có kích thước ​3×7​,và chúng ta áp dụng nó vào vùng ​3×7 ở giữa. Phần tử trung vị trong vùng đó là ​3​, nên sau khi áp dụng lưới sẽ trở thành

9 8 8 8 7 7 7 8 7

1 3 3 3 3 3 3 3 4

2 3 3 3 3 3 3 3 9

3 3 3 3 3 3 3 3 7

7 7 7 7 7 7 8 8 8

Chú ý rằng ​X​ và Y ​là số lẻ, nên chỉ có một số nguyên là phần tử trung vị.

Nam muốn dùng dụng cụ san bằng đó nhiều lần để độ cao tất cả các ô đều như nhau. Hơn nữa, anh ta cũng muốn biết độ cao cuối cùng lớn nhất có thể. Độ cao lớn nhất có thể anh ta có thể đạt được là bao nhiêu ?

Ngoài ra, bạn có ​Q ​truy vấn, các truy vấn có có cặp X ​và Y ​khác nhau.

Dữ liệu vào:

·         Dòng đầu tiên chứa 3 số nguyên ​N​, ​M​, ​Q​.

·         N dòng tiếp theo thể hiện các độ cao. Mỗi dòng chứa ​M số nguyên. Giá trị thứ ​j ở dòng thứ ​i là ​H​_i,j.​

·         Q ​dòng tiếp theo là các truy vấn. Dòng thứ ​j chứa 2 số nguyên ​X​_j và ​Y_j​.

Dữ liệu ra:

Với mỗi truy vấn, in ra một dòng, chiều cao chung lớn nhất Nam có thể đạt được nếu dùng dụng cụ san bằng kích thước ​X​_j× Y_j​.

Ràng buộc:

● 3​≤​N​,​M​≤​1000

● 1​≤​Q​≤​25

● 0​≤​H_i,j ​≤ ​10​⁷

● 3​≤​X≤ ​N

●   3​≤Y​≤ ​M

●   Y_j và X_j ​là số lẻ.

Ví dụ:

EQUALIZE.INP	EQUALIZE.OUT
3 7 3 8 5 5 5 8 6 8 8 9 5 5 5 9 8 8 6 8 5 5 5 8 3 3 3 5 3 7	8 5 6

Giải thích:

Trong truy vấn đầu tiên, Nam có thể kết thúc với độ cao bằng 8 bằng việc san bằng vùng ​3× 3 bên trái nhất:

8 8 8 5 8 6 8

8 8 8 5 5 9 8

8 8 8 5 5 5 8

Sau đó là ​vùng ​3 × 3​ bên phải nhất:

8 8 8 5 8 8 8

8 8 8 5 8 8 8

8 8 8 5 8 8 8

Kết thúc bằng ​vùng ​3× 3​ ở trung tâm:

8 8 8 8 8 8 8

8 8 8 8 8 8 8

8 8 8 8 8 8 8

Có thể thấy rằng đây là độ cao lớn nhất có thể đạt được.

Test Solotion