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

Ngọc có 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ị ô nằm trên giao của dòng $i$ và cột $j$ của bảng số gọi 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)$, hãy 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$. Hình chữ nhật gồm các ô thuộc một đoạn dòng liên tiếp và một đoạn cột liên tiếp của bảng; diện tích là số ô của nó.

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.

Dữ liệu vào

• 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},\dots ,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.

Dữ liệu ra

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

Ràng buộc

• $1\le M,N\le 1000$
• $0\le a_{ij}\le 2$
• $1\le K\le {10}^6$
• $1\le p_i\le q_i\le M$

Subtasks

• Subtask 1 ($20\%$ số điểm): $N=1$, $M\le 100$, $K\le 100$.
• Subtask 2 ($40\%$ số điểm): $M,N\le 100$.
• Subtask 3 ($40\%$ số điểm): $M,N\le 1000$, $K\le {10}^6$.

Ví dụ