Description
Susu, a clever and adorable child in class B29 of Happiness Kindergarten, loves drawing and reading, especially the works of Thomas H. Cormen. Susu has a giant bookshelf with $R$ rows and $C$ columns. Each position on the bookshelf holds a book, and the book at the $i$-th row from the top and $j$-th column from the left has a thickness of $P_{i,j}$ pages.
Besides reading, Susu has another essential task: picking apples. Every day, she must pick a specific apple. Some apples on the tree are high and some are low, but no matter what, Susu cannot reach them on her own. However, she discovered that if she places a few books under her feet, she can reach the apple. She also noticed that for the apple specified on day $i$, she can definitely reach it as long as the total number of pages of the books she places under her feet is at least $H_i$.
Because there are too many books on the shelf, her parents are worried that Susu might finish reading all the books in one day and neglect kindergarten, so they only allow her to take books from a specific area each day. This area is a rectangle. For day $i$, the top-left corner of the given area is the book at the $i$-th row from the top and $y_{1i}$-th column from the left, and the bottom-right corner is the book at the $x_{2i}$-th row from the top and $y_{2i}$-th column from the left. In other words, on that day, Susu can only choose a number of books from the $(x_{2i} - x_{1i} + 1) \times (y_{2i} - y_{1i} + 1)$ books available to place under her feet to pick the apple.
Susu always returns the books to their original places after each use, and her bookshelf will not have books removed or replaced. The apple-picking task lasts for $M$ days. Given the number of pages for each book and the daily area restrictions and picking requirements, tell Susu the minimum number of books she needs to take each day to pick the specified apple.
Input
The first line contains three positive integers $R, C, M$.
The next $R$ lines each contain $C$ integers, representing the page counts $P_{i,j}$ of the books from top to bottom and left to right.
The next $M$ lines each contain five positive integers $x_{1i}, y_{1i}, x_{2i}, y_{2i}, H_i$, representing the rectangular area defined by $(x_{1i}, y_{1i})$ and $(x_{2i}, y_{2i})$ for day $i$, with a requirement that the total page count must be at least $H_i$.
It is guaranteed that $1 \le x_{1i} \le x_{2i} \le R$ and $1 \le y_{1i} \le y_{2i} \le C$.
Output
Output $M$ lines. The $i$-th line should contain the minimum number of books Susu needs to take on day $i$ to pick the apple. If it is impossible to pick the apple even by taking all the books in the area, output "Poor QLW" (without quotes).
Examples
Input 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 1
6 15 2 Poor QLW 9 1 3
Input 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 2
6 7 3 10 Poor QLW 1 2
Constraints
- 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 200,000$.
- For another 50% of the data: $R = 1, C \le 500,000, M \le 20,000$.
- For 100% of the data: $1 \le P_{i,j} \le 1,000, 1 \le H_i \le 2,000,000,000$.