Vườn nho (Grapevine)

Nguồn: UVa

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho ma trận độ cao $H$ kích thước $N\times M$. Các giá trị không giảm khi đi từ trái sang phải trên mỗi hàng và cũng không giảm khi đi từ trên xuống dưới trên mỗi cột.

Với mỗi truy vấn $[L,U]$, hãy chọn một hình vuông con gồm các hàng liên tiếp và các cột liên tiếp. Tất cả các ô trong hình vuông phải có độ cao thuộc đoạn:

Input

Dòng đầu chứa $N$ và $M$.

$N$ dòng tiếp theo, mỗi dòng chứa $M$ số nguyên của ma trận.

Dòng tiếp theo chứa $Q$.

$Q$ dòng tiếp theo, mỗi dòng chứa $L$ và $U$.

Output

Với mỗi truy vấn, in một số nguyên là cạnh lớn nhất của hình vuông hợp lệ. Nếu không có ô nào hợp lệ, in 0.

Subtask

• Subtask 1 — 20%: $N,M\le40$, $Q\le100$.
• Subtask 2 — 30%: $N,M\le200$, $Q\le1000$.
• Subtask 3 — 50%: $N,M\le500$, $Q\le10000$.

Trong mọi Subtask: $0\le H_{i,j}\le10^5$, $0\le L\le U\le10^5$ và ma trận không giảm theo hàng, cột.

Ví dụ

Input

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

Output

3
2
4

Giải thích

• Với $[22,90]$, cạnh lớn nhất là $3$.
• Với $[33,35]$, cạnh lớn nhất là $2$.
• Với $[20,100]$, toàn bộ một hình vuông $4 imes4$ phù hợp, nên đáp án là $4$.