Sau một tuần tưng bừng, náo nức với các hoạt động của ngày hội học sinh, sinh viên Việt Nam 9/1, Coder Bắc nhận ra rằng cậu ta còn khá nhiều bài tập cần phải giải quyết. Một trong những bài tập đó là bài toán lập trình với bảng số khá phức tạp như sau:

Thầy giáo cho một bảng số 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. Giao của dòng \(i\) và cột \(j\) gọi là ô (i,j), có giá trị là \(a_{ij}\) (\(0 \leq a_{ij} \leq 2\)). Thầy đưa ra truy vấn sau đây đối với bảng số: Cho hai số nguyên \(p\) và \(q\ (1 \leq p \leq q \leq \ m)\), hãy cho biết diện tích lớn nhất của hình chữ 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 (diện tích của một hình chữ là số lượng các ô tạo ra hình chữ nhật đó).

Yêu cầu: Cho \(k\) bộ truy vấn \(p_{i},\ q_{i}\ (i\ = \ 1,\ 2,\ \ldots,\ k)\). Với mỗi truy vấn \(p_{i},\ q_{i}\) hãy tính diện tích hình chữ nhật lớn nhất theo yêu cầu bài toán.

Dữ liệu vào:

- Dòng đầu tiên gồm hai số nguyên \(m,\ n\ (1\ \leq m,\ n \leq \ 1000);\)

- \(m\) dòng tiếp theo, dòng thứ \(i\ \)chứa \(n\) số \(a_{i1},\ a_{i2},\ \ldots,\ a_{in}\);

- Dòng tiếp theo chứa số nguyên \(k\ \left( 1 \leq k \leq 10^{6} \right);\)

- \(k\) dòng tiếp theo chứa 2 số nguyên \(p_{i}\) và \(q_{i}\) biểu diễn truy vấn thứ \(i\) (\(1 \leq p_{i} \leq q_{i} \leq m\));

Kết quả:

+ Ghi ra \(k\ \)dòng, mỗi dòng ghi kết quả tương ứng với mỗi truy vấn.

Ví dụ:

Giới hạn:

- Subtask 1: tương ứng 23 tests có\(\ n\ = \ 1,\ m\ \leq \ 100,\ k\ \leq \ 100\);

- Subtask 2: tương ứng 24 tests có \(m,n\ \leq \ 100\), \(k \leq 10^{4}\);

- Subtask 3: tương ứng 23 tests có \(m,n\ \leq \ 1000,\ k \leq 10^{6}\).