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~.

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

Output

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

Scoring

Sample Input 1

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

Sample Output 1

3
4
6