Problem Description

In the Happy Kindergarten B29 class, Su Su is a smart, lovely, and well-behaved child. Her hobbies include drawing and reading, especially the articles by Thomas H. Cormen. Su Su has a giant bookshelf at home with $R$ rows and $C$ columns. Each position on the bookshelf holds a book, and the book in the $i$-th row from the top and $j$-th column from the left has $P_{i,j}$ pages.

Besides reading, Su Su has a daily task of picking apples. She must pick a designated apple each day. The apples on her family's tree are at varying heights, and Su Su, being short, cannot reach them on her own. However, she notices that by placing a few books under her feet, she can reach the apples. She observes that for the designated apple on the $i$-th day, she can pick it as long as the total number of pages of the books she places under her feet is not less than $H_i$.

Due to the large number of books on the shelf, her parents are concerned that she might read all the books in one day and miss going to kindergarten. Therefore, they allow her to take books only from a specific area each day. This area is a rectangle, and on the $i$-th day, the top-left corner of the area is the book in the $x1_i$-th row from the top and $y1_i$-th column from the left, and the bottom-right corner is the book in the $x2_i$-th row from the top and $y2_i$-th column from the left. In other words, on the $i$-th day, Su Su can only choose from the $(x2_i - x1_i + 1) \times (y2_i - y1_i + 1)$ books in this area to place under her feet to pick the apple.

Su Su always returns the books to their original positions promptly, and her bookshelf does not have any books removed or added. The task of picking apples will continue for $M$ days. Given the number of pages of each book and the daily area restrictions and picking requirements, please tell Su Su how many books she needs to take at least each day to pick the designated apple.

Input Format

The first line contains three positive integers $R, C, M$.

The next $R$ lines, each with $C$ integers, give the number of pages $P_{i,j}$ for each book from top to bottom and left to right.

The next $M$ lines, each containing five positive integers $x1_i, y1_i, x2_i, y2_i, H_i$, describe the designated area for the $i$-th day as a rectangle between $(x1_i, y1_i)$ and $(x2_i, y2_i)$, with the requirement that the total number of pages must be at least $H_i$.

It is guaranteed that $1 \le x1_i \le x2_i \le R$ and $1 \le y1_i \le y2_i \le C$.

Output Format

Output $M$ lines. The $i$-th line should answer how many books Su Su needs to take at least on the $i$-th day to pick the apple. If it is impossible to pick the apple even by taking all the books, output Poor QLW on that line.

Sample Input and Output

Input Sample #1

5 5 7
14 15 9 26 53
58 9 7 9 32
38 46 26 43 38
32 7 9 50 28
8 41 9 7 17
1 2 5 3 139
3 1 5 5 399
3 3 4 5 91
4 1 4 1 33
1 3 5 4 185
3 3 4 3 23
3 1 3 3 108

Output Sample #1

6
15
2
Poor QLW
9
1
3

Input Sample #2

1 10 7
14 15 9 26 53 58 9 7 9 32
1 2 1 9 170
1 2 1 9 171
1 5 1 7 115
1 1 1 10 228
1 4 1 4 45704571
1 1 1 1 1
1 7 1 8 16

Output Sample #2

6
7
3
10
Poor QLW
1
2

Notes/Hints

For $10\%$ of the data, $R, C \le 10$.

For $20\%$ of the data, $R, C \le 40$.

For $50\%$ of the data, $R, C \le 200$, $M \le 2 \times 10^5$.

For another $50\%$ of the data, $R = 1$, $C \le 5 \times 10^5$, $M \le 2 \times 10^4$.

For $100\%$ of the data, $1 \le P_{i,j} \le 1000$, $1 \le H_i \le 2 \times 10^9$.

见题面 Input 部分

见题面 Output 部分