Apple Picking and Book Stack

In this problem, little Sushu from Class B29 of Happy Kindergarten has a giant bookshelf with $R$ rows and $C$ columns, where the book in the i-th row and j-th column has $P_{i,j}$ pages. Every day, besides reading, Sushu must pick an apple from a tree. She realized that if she stacks some books underneath her feet (by summing up their page counts) and the total is at least $H_i$ (a given threshold for day i), then she can reach the apple.

However, her parents restrict her to only use books from a specific rectangular region of her bookshelf on each day. For the i-th day, the allowed region is defined by its top-left corner located at row $x1_i$, column $y1_i$ and bottom-right corner at row $x2_i$, column $y2_i$. In other words, only the $(x2_i - x1_i + 1) \times (y2_i - y1_i + 1)$ books in that submatrix can be selected.

Sushu may take any book (and she always returns it immediately after using it), which means she can pick the same book more than once in a day if necessary. Your task is to determine, for each day, the minimum number of books Sushu must take from the allowed region so that the sum of the pages is at least $H_i$. It is optimal for her to repeatedly pick the book with the maximum number of pages in the allowed region.

The answer for each day is computed as:

\[ \text{answer} = \left\lceil\frac{H_i}{\max_{(i,j) \in \text{region}} \; P_{i,j}}\right\rceil \]

inputFormat

The first line contains two integers R and C --- the number of rows and columns of the bookshelf. Then follow R lines, each containing C integers where the j-th integer in the i-th line is $P_{i,j}$, the number of pages of the book in that position.

The next line contains a single integer M, the number of days (queries). Each of the following M lines contains five integers: x1, y1, x2, y2, and H, describing the allowed submatrix (with 1-indexed rows and columns) and the required minimum total pages for that day.

outputFormat

For each day, output a single integer on a separate line --- the minimum number of books Sushu must take so that the total number of pages is at least H.

sample

3 3
1 2 3
4 5 6
7 8 9
2
1 1 3 3 10
2 2 3 3 15

2
2

</p>