Jiajia has an $n \times n$ black and white chessboard. Each cell has two sides, one white and one black. Jiajia places the chessboard flat on a table, so exactly one side of each cell is facing up, as shown in the figure below:

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

If two cells of the same color share a common edge, we say these two cells belong to the same connected component. The figure above has 5 black connected components and 3 white connected components.

Jiajia can flip one cell every minute (i.e., white becomes black, and black becomes white), and then calculate the current number of black connected components and white connected components. Can you calculate this faster?

Input

The first line of the input contains a positive integer $n$, the side length of the grid. The following $n$ lines each contain $n$ integers, either 0 or 1, representing the initial state. 0 represents white, and 1 represents black. The next line contains an integer $m$, the number of operations. The following $m$ lines each contain two integers $x, y$ ($1 \le x, y \le n$), representing flipping the cell at coordinates $(x, y)$.

Output

The output contains $m$ lines, each corresponding to an operation. Each line includes two integers $b, w$, representing the number of black regions and white regions, respectively.

Constraints

• $1 \le n \le 200$
• $1 \le m \le 10,000$

Examples

Input 1

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

Output 1

4 3
5 2

Note

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

There are 4 black regions and 3 white regions

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

There are 5 black regions and 2 white regions