표준 문제 | cho.sh

N행 M열의 표가 주어진다. 각 칸에는 0 또는 1이 들어 있다.

여러 질의가 주어진다. 각 질의는 위쪽 행 r1과 아래쪽 행 r2를 지정한다. 답으로 선택하는 직사각형은 모든 행이 r1부터 r2까지의 범위 안에 있어야 하며, r1행과 r2행도 사용할 수 있다. 이 범위 밖의 행은 사용할 수 없다.

각 질의마다 모든 칸이 0인 직사각형 중 넓이가 가장 큰 것의 넓이를 구하라. 직사각형의 변은 표의 행과 열에 평행하며, 넓이는 포함한 칸의 개수이다.

첫째 줄에 표의 크기 N과 M이 공백으로 구분되어 주어진다.

다음 N개의 줄에는 각 줄마다 M개의 수가 공백으로 구분되어 주어진다. 각 수는 0 또는 1이다.

그다음 줄에 질의의 수 Q가 주어진다. 다음 Q개의 줄에는 각 질의의 위쪽 행과 아래쪽 행을 나타내는 두 정수 r1, r2가 공백으로 구분되어 주어진다.

각 질의마다 한 줄에 하나의 정수를 출력한다. 이 정수는 주어진 행 범위 안에 놓을 수 있는 가장 큰 0 직사각형의 넓이이다.