Truy vấn trên bảng số

Ngọc có một bảng số nguyên có kích thước \(M \times N\). Các dòng được đánh số từ \(1\) đến \(M\) từ trên xuống dưới, các cột được đánh số từ \(1\) đến \(N\) từ trái sang phải. Giá trị của ô nằm trên giao của dòng \(i\) và cột \(j\) của bảng số là \(a_{ij}\) (\(0 \le a_{ij} \le 2\)).

Mỗi truy vấn trên bảng số cho biết hai số nguyên \(p\) và \(q\) (\(1 \le p \le q \le M\)). Yêu cầu là tìm hình chữ nhật có diện tích lớn nhất gồm các ô nằm trong phạm vi từ dòng thứ \(p\) đến dòng thứ \(q\) của bảng số mà trong đó chênh lệch giữa phần tử lớn nhất và phần tử nhỏ nhất không vượt quá \(1\).

Yêu cầu: Cho \(K\) truy vấn, với mỗi truy vấn \(p, q\) hãy đưa ra diện tích hình chữ nhật tương ứng tìm được.

Input

• Dòng đầu tiên có hai số nguyên \(M, N\) (\(1 \le M, N \le 1000\)).
• \(M\) dòng tiếp theo, dòng thứ \(i\) chứa \(N\) số nguyên \(a_{i1}, a_{i2}, \ldots, a_{iN}\).
• Dòng tiếp theo chứa số nguyên \(K\) (\(1 \le K \le 10^6\)).
• \(K\) dòng tiếp theo chứa hai số nguyên \(p_i\) và \(q_i\) biểu diễn truy vấn thứ \(i\) (\(1 \le p_i \le q_i \le M\)).

Các số trên cùng một dòng cách nhau bởi dấu cách.

Output

• Gồm \(K\) dòng, mỗi dòng ghi kết quả tương ứng với mỗi truy vấn.

Example

3 3
0 1 1
1 1 2
2 2 2
3
1 1
1 2
1 3

3
4
6

Scoring

• Có 20% số điểm tương ứng với \(N = 1, M \le 100, K \le 100\);
• Có 40% số điểm tương ứng với \(M, N \le 100\);
• Có 40% số điểm tương ứng với \(M, N \le 1000, K \le 10^6\).