Maximum Water Volume in a Garden

You are given a 2D grid representing the heights of various cells in a garden. In this garden, water is collected in ponds formed by sub-grids. For each query, a sub-grid is specified by its top-left corner and its side length. The maximum volume of water that can be held in that pond is defined as the difference between the highest and the lowest cell heights in the sub-grid.

Mathematically, for a given sub-grid, the volume is calculated as:

$$V = \max - \min$$

where \(\max\) and \(\min\) are the maximum and the minimum heights in the specified sub-grid, respectively. All indices in the queries are 1-indexed.

Your task is to process multiple queries over the grid and output the computed volume for each query.

inputFormat

The input is read from standard input (stdin) and has the following format:

1. The first line contains two integers \(n\) and \(m\), representing the number of rows and columns of the grid.
2. The next \(n\) lines each contain \(m\) space-separated integers, representing the grid of heights.
3. The following line contains a single integer \(q\), the number of queries.
4. Each of the next \(q\) lines contains three integers \(x\), \(y\) and \(s\). Here, \(x\) and \(y\) specify the top-left corner of a sub-grid (1-indexed), and \(s\) is the side length of the sub-grid.

outputFormat

For each query, output a single integer on a new line representing the maximum volume of water that can be held in the corresponding sub-grid.

## sample

5 5
1 2 3 4 5
5 -1 0 1 2
4 3 6 -2 1
5 5 7 3 2
10 -6 -5 4 1
1
1 1 3

7

</p>