Janko is preparing for the final match of the World Cup 2022. However, there is a large traffic jam in Doha, since all fans are going to the match. To make matters worse, Janko’s hotel is in a different part of the city from the stadium.

It is known that Doha looks like a matrix of dimensions \(N \times M\). With field \((i,j)\) we denote a field in the \(i\)-th row and \(j\)-th column. Janko’s hotel is on the field \((1,1)\), while the stadium is on the field \((N, M)\). On each field of the matrix (including \((1,1)\) and \((N, M)\)), there is a group of fans - on the field \((i,j)\) there are exactly \(a_{i,j}\) fans.

Janko can move from field \((i,j)\) either to field \((i+1,j)\) or \((i,j+1)\) (if the corresponding destination is within the matrix boundaries). Since Janko doesn’t like crowds, he decided to plan his path in such a way as to meet as few fans as possible (where the number of fans he meets is the sum of all \(a_{i,j}\) over the fields he visited on his path to the stadium).

As soon as he made his plan, on the news he heard that exactly one field will be blocked for the public, and therefore he won’t be able to go through that field on his path to the stadium. Unfortunately, Janko isn’t certain which field will be blocked and he asks you to answer \(Q\) different queries. In the \(i\)-th query, Janko wants to know how many fans will he need to meet if field \((x_i,y_i)\) is blocked.

Input format

The first line of standard input contains two integers, \(N\) and \(M\), representing the dimensions of Doha.

Line \(i\) of the following \(N\) lines contains \(M\) integers, \(j^{th}\) of them is \(a_{i,j}\) - number of fans on field \((i,j)\).

The following line contains one integer, \(Q\), representing the number of queries that Janko will ask.

The following \(Q\) lines contain two integers, \(x_i\) and \(y_i\), describing the field that will be blocked in the \(i^{th}\) query.

Output format

Your program should print \(Q\) lines to the standard output, each of them containing one integer. In line \(i\), you should print the minimal number of fans that Janko will have to meet on his path to the stadium, if the field \((x_i,y_i)\) gets blocked.

Example 1

Input

3 4
1 2 3 4
5 6 7 8
9 10 11 12
2
1 2
2 4

Output

39
36

Explanation

• The first query: If the field \((1,2)\) is blocked, optimal path for Janko is \((1,1) \rightarrow (2,1) \rightarrow (2,2) \rightarrow (2,3) \rightarrow (2,4) \rightarrow (3,4)\). On that path, he will meet \(39\) fans.
• The second query: If the field \((2,4)\) is blocked, optimal path for Janko is \((1,1) \rightarrow (1,2) \rightarrow (1,3) \rightarrow (2,3) \rightarrow (3,3) \rightarrow (3,4)\). On that path, he will meet \(36\) fans.

Constraints

• \(2 \leq N, M\).
• \(4 \leq N \cdot M \leq 10^6\).
• \(1 \leq Q \leq 5 \cdot 10^5\).
• \(1 \leq a_{i,j} \leq 10^9\).
• \(1 \leq x_i \leq N\).
• \(1 \leq y_i \leq M\).
• It is guaranteed that fields with the hotel or stadium will never be blocked and that Janko will always be able to reach the stadium from his hotel.

Test cases are split into five disjoint groups:

• In tests worth 15 points: \(N = 2\).
• In tests worth 10 points: \(Q \leq 100\), \(N, M \leq 7\).
• In tests worth 15 points: \(Q \leq 2000\), \(N \cdot M \leq 2000\).
• In tests worth 20 points: \(Q \leq 10^4\).
• In tests worth 40 points: no additional constraints.