Description

There is an $n \times n$ grid maze consisting only of digits $0$ and $1$. If you are on a cell with $0$, you may move to one of the 4 adjacent cells with $1$. Similarly, if you are on a cell with $1$, you may move to one of the 4 adjacent cells with $0$.

Your task is: for the given maze, for each specified starting cell, determine how many cells are reachable (including the starting cell).

Input Format

The first line contains two positive integers $n,m$.

The next $n$ lines each contain $n$ characters, each of which is either $0$ or $1$, with no spaces between characters.

Then follow $m$ lines. Each line contains two positive integers $i,j$, referring to the cell at row $i$, column $j$ of the maze, asking how many cells are reachable starting from this cell.

Output Format

Output $m$ lines. For each query, print the corresponding answer.

2 2
01
10
1 1
2 2

4
4

Hint

For the sample, all cells are mutually reachable.

• For $20\%$ of the testdata, $n \leq 10$.
• For $40\%$ of the testdata, $n \leq 50$.
• For $50\%$ of the testdata, $m \leq 5$.
• For $60\%$ of the testdata, $n,m \leq 100$.
• For $100\%$ of the testdata, $1\le n \leq 1000$, $1\le m \leq 100000$.

Translated by ChatGPT 5