# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

You have a grid with n rows and m columns. Cell at the i^{th} row and the j^{th} column is called Cell(i, j) and id of the cell is G­_{i,j}. Each cell has a unique id from 1 to n*m. You can jump from Cell(i,j) to Cell(x,y) by consuming power {(i-x) ^{2}+(j-y)^{2}}*(G

Input starts with two integers n and m.

Each of the next n lines contain m integers representing the grid.

Then the next line contains one integer Q, representing the number of days.

The next Q lines will have the information of each day. In each line, there will be two id p and q.

**Constrains**

1 ≤ n, m ≤ 300

1 ≤ Q ≤ 10^{5}

1 ≤ p ≤ q ≤ n*m

For each day, you have to output minimum power on a line by itself.

Input | Output |
---|---|

3 3 1 4 3 2 5 7 8 9 6 4 4 8 6 9 5 8 1 9 | 9 3 6 12 |

**Explanation:**

In the last day, you want to go from 1^{st} cell to 9^{th}. You can select 1,2,4,8 as the candidate values for D for that day. Otherwise you can not go from 1^{st} cell to 9^{th} cell.

If you select 2 as D, you have to go through 1,3,5,7,9. The cost will be {(1-1)^{2}+(1-3)^{2}}*(3-1)+ {(1-2)^{2}+(3-2)^{2}}*(5-3)+ {(2-2)^{2}+(2-3)^{2}}*(7-5)+ {(2-3)^{2}+(3-2)^{2}}*(9-7)=18.

If you select 4 as D, you have to go through 1,5,9. The cost will be {(1-2)^{2}+(1-2)^{2}}*(5-1)+ {(2-3)^{2}+(2-2)^{2}}*(9-5) =12.

If you select 8 as D, you have to go through 1,9. The cost will be {(1-3)^{2}+(1-2)^{2}}*(9-1) =40

So, the minimum cost will be 12.

Login to submit