Description
Megumin knows only one spell, but it is the most powerful one in the world: Explosion. It drains all of her mana, so she can cast it only once a day. Afterward, she collapses on the spot, and Kazuma, her party leader, has to carry her back to the town of Axel.
Lately, the plains outside Axel have been overrun by giant toads. The plains are divided into an grid, and cell contains giant toads.
To make her single daily cast count, Megumin has invented a new version of her beloved spell: the X-plosion. When she targets cell , the blast travels along both diagonals through that cell, all the way to the edges of the plains:
- The diagonal running from top-left to bottom-right through .
- The diagonal running from top-right to bottom-left through .
Every giant toad on these two diagonals is blown away. The target cell lies on both diagonals, but its toads can only be blown away once.
Kazuma does not want to carry her home after a disappointing cast, so he has written down candidate target cells to compare. Since Megumin will not cast until he has chosen a target, each candidate is evaluated independently on the original plains. Help him by writing a program that calculates, for each candidate, how many giant toads the X-plosion would blow away.
(Note: The grid is 0-indexed. Cell is in row and column , so the top-left cell is and the bottom-right cell is . Likewise, is the row index and is the column index of the target cell.)
Input
The first line contains two space-separated integers, and , representing the size of the plains and the number of candidate targets, respectively.
The next lines describe the plains. The -th of these lines () contains integers .
The following lines describe the candidates. Each line contains two integers and , representing one candidate target cell .
Constraints
Subtasks
- Subtask 1 (Testcase 1–3): , .
- Subtask 2 (Testcase 4–6): .
- Subtask 3 (Testcase 7–10): No additional constraints.
Output
For each of the candidates, output a single integer on a new line: the number of giant toads that the X-plosion would blow away.
Sample Explanation
For the first candidate , the X-plosion would hit the cells marked with square brackets:
[1] 2 [3] 4
5 [6] 7 8
[9] 1 [2] 3
4 5 6 [7]
The target cell lies on both diagonals, but its toads are counted only once, so the answer is .
For the second candidate , the X-plosion would hit the marked cells:
1 2 [3] 4
5 [6] 7 [8]
[9] 1 2 3
4 5 6 7
The answer is . The first candidate's X-plosion would also hit cells , , and , but since each candidate is evaluated independently, their toads are counted again.