Description

Jiajia has an $n \times n$ black-and-white board. Each cell has two faces: one white and one black. Jiajia lays the board flat on the table, so exactly one face of each cell is up, as shown in the figure below:

We number the rows from top to bottom as $1, 2, 3, \ldots, n$, and the columns from left to right as $1, 2, 3, \ldots, n$. Thus, each cell can be represented by board coordinates $(x, y)$. In the figure above, there are $8$ cells with the black side up, and the other $17$ cells have the white side up.

If two cells of the same color share a common edge, we say these two same-colored cells belong to the same connected component. In the figure above, there are $5$ black connected components and $3$ white connected components.

Jiajia can flip one cell per minute (i.e., white becomes black, and black becomes white), then count how many black connected components and white connected components there are. Can you compute it faster?

Input Format

The first line contains a positive integer $n$, the side length of the board.
Each of the next $n$ lines contains $n$ integers, each either $0$ or $1$, representing the initial state. $0$ means white, and $1$ means black.

The next line contains an integer $m$, the number of operations.
Each of the next $m$ lines contains two integers $x$, $y$ ($1 \le x, y \le n$), indicating to flip the cell at coordinates $(x, y)$.

Output Format

Output contains $m$ lines, one for each operation. Each line contains two integers $b$, $w$, denoting the numbers of black connected components and white connected components.

5
0 1 0 0 0
0 1 1 1 0
1 0 0 0 1
0 0 1 0 0
1 0 0 0 0
2
3 2
2 3

4 3
5 2

Hint

【Sample Explanation】

After flipping $(3, 2)$, the board becomes:

There are $4$ black connected components and $3$ white connected components.

After flipping $(2, 3)$, the board becomes:

There are $5$ black connected components and $2$ white connected components.

【Constraints】
For $100\%$ of the testdata, $1 \le n \le 200$, $1 \le m \le 10^4$.

Translated by ChatGPT 5