Các thành phố ở Alberta thường được quy hoạch thành một lưới chữ nhật gồm nhiều khu phố. Hàng được đánh số từ 0 đến R - 1 theo hướng bắc xuống nam, còn cột được đánh số từ 0 đến C - 1 theo hướng tây sang đông.

Mỗi khu phố có một hạng chất lượng sống riêng biệt từ 1 đến R * C; hạng 1 là tốt nhất và hạng R * C là tệ nhất.

Sở quy hoạch muốn chọn một hình chữ nhật gồm H hàng và W cột sao cho trung vị của các hạng chất lượng trong hình chữ nhật là tốt nhất, tức nhỏ nhất có thể. H và W đều là số lẻ, lần lượt không vượt quá R và C.

Với một tập có số phần tử lẻ, trung vị là phần tử m sao cho số phần tử tốt hơn m bằng số phần tử tệ hơn m.

Bạn cần cài đặt hàm rectangle(R, C, H, W, Q). Trong đó Q[a][b] là hạng chất lượng của khu phố ở hàng a, cột b. Hàm phải trả về trung vị nhỏ nhất có thể trong mọi hình chữ nhật kích thước H nhân W.

Bộ chấm chỉ gọi rectangle một lần trong mỗi test.

Ví dụ 1

Với R = C = 5, H = W = 3 và

5 11 12 16 25
17 18 2 7 10
4 23 20 3 1
24 21 19 14 9
6 22 8 13 15

Hình chữ nhật 3 nhân 3 ở giữa bên phải có trung vị 9, và không có hình chữ nhật hợp lệ nào có trung vị tốt hơn. Do đó hàm trả về 9.

Ví dụ 2

Với R = 2, C = 6, H = 1, W = 5 và

6 1 2 11 7 5
9 3 4 10 12 8

Đáp án là 5.

Các nhóm điểm

Trong mọi nhóm, 1 <= H <= R, 1 <= W <= C, H và W là số lẻ, và Q là một hoán vị của các số từ 1 đến R * C.

Chi tiết cài đặt

Bạn cần nộp một tệp C++ cài đặt:

int rectangle(int R, int C, int H, int W, int Q[3001][3001]);

Tệp của bạn được biên dịch cùng quality.h. Chương trình của bạn không được định nghĩa hàm main.