Description
Because Squidward’s had enough of living with the “good neighbors”, he moved out of Bikini Bottom. SpongeBob and Patrick wanna apologize to him and persuade him to come back. So they go to Tentacle Acres, where Squidward is living now.
After arrving there, they shortly find out there are a lot of octopuses gathering on the street. Specifically, there are n rows of m octopuses on the street.
Spongebob thinks that Squidward must be one of the octopuses there. But all of them look like Squidward, it’s too hard to find out who is Squidward. Fortunately Patrick brings the book – “How to find out Squidward”.
Thanks to the book, they know Squidward has a big nose. Hence the octopus with a big nose probably is Squidward. Now you are given the size of all the octopuses’ noses. The size of the j-th octopus’s nose in row i is aij. Spongebob and Patrick need you to find out the octopus with the biggest nose from the l-th octopus to the r-th octopus in the row u, row (u+1), …, row d (you only need to output the biggest size).
You have to help Spongebob and Patrick q times.
Subtask
- for testcase 1~2: n = 1, aij = 1
- for testcase 3~5: n = 1
- for testcase 6~10: no additional restriction
Note
You don't need to store all the query(i.e. all the u, d, l, r) and output the answers together in the end. When you get a query, you can just output the answer for the query immediately.
You can reference the following code.
Input
The first line contains two integer n, m (1 ≤ n, m ≤ 100) – the number of rows and the number of octopuses in a row.
The following n lines contain m integers each, the j-th element in the i-th line aij is the size of the j-th octopus's nose in row i (1 ≤ aij ≤ 100).
Next line contain a integer q (1 ≤ q ≤ 100) – the times you have to help Spongebob and Patrick.
Then q lines follow. Each line contains four integer u, d, l, r (1 ≤ u ≤ d ≤ n, 1 ≤ l ≤ r ≤ m) – the range of octopuses you have to find out the biggest size of noses.
Output
For each time you help Spogebob and Patrick, output the biggest size of noses.
Remember to print a newline('\n') at the end of the last line.