Computer Virus
Tag(s):

Data Structures, Medium

Problem
Editorial
Analytics

Oh no! The virus infected Nick's computer after he downloaded a bunch of TAS preparation books from BayPirate, and now he needs your (the best programmer in Lalalandia's) help!

The virus encrypted the data, closed all the programs, and only thing Nick sees on his screen is the matrix with $N * M$ cells each containing $0$ or $1$ only. All cells also have color. Initially all the cells are black.

Then virus opens $Q$ windows. In the $i$th window, Nick sees coordinates of two points: $x_1$, $y_1$ and $x_2$, $y_2$, respectively. This means that the virus paints all the cells, which are between these points, in white. More formally, let $x$ and $y$ be the coordinates of the cell, then the program will paint it in white only if $x_1 \le x \le x_2$ and $y_1 \le y \le y_2$. After the painting, each window requires the password, which is the maximal area $A$ of the rectangle, which has at least one $1$ in each column and all of its cells are white. Note that all windows are independent, so if the cell is painted white in one window, it will not be painted in all other windows.

Can you help Nick with this tricky problem?

Input format

The first line contains 2 integers: $N$ and $M$ - the number of rows and columns, respectively.

The next $N$ lines describe the matrix: each contains $M$ numbers of $0$ or $1$ only, without separating spaces (see the samples for more explanation).

The next line consists of integer $Q$ - the number of windows. Next $Q$ lines describe the $i$ th window: each contains the coordinates of the left and right boundaries $x_1, y_1$ and $x_2, y_2$.

Output format

The $Q$ lines should each contain single integer $A$ - the password for the window $i$ ($1 \le i \le Q$).

Constraints:

$1 \le N \le 2000$, $1 \le N * M \le 4000000$

$1 \le Q \le 1000000$

$1 \le x_1 \le x_2 \le N$, $1 \le y_1 \le y_2 \le M$

SAMPLE INPUT
4 4
0000
0010
0100
1000
1
1 2 3 4

SAMPLE OUTPUT
6
Explanation

In the first window, the virus will paint the following cells in white:

We can choose this rectangle with area 6, because it has one $1$ in each row:

so our answer is $6$.

Time Limit: 3.0 sec(s) for each input file.
Memory Limit: 512 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...

Contributor

Challenge Name

HackerEarth Collegiate Cup Second Elimination

OTHER PROBLEMS OF THIS CHALLENGE
• Data Structures > Advanced Data Structures
• Math > Linear Algebra
• Math > Number Theory
• Algorithms > Sorting
• Data Structures > Advanced Data Structures
• Algorithms > Graphs
• Algorithms > String Algorithms
• Algorithms > Graphs