Flipped Go: Counting Captured White Stones

The game of Go is played on an \(n \times n\) board with intersections where stones are placed. Each stone is either black or white. A stone (or a connected group of stones of the same color) is said to be \(alive\) if at least one stone in that group is adjacent (up, down, left, or right) to an empty intersection (called a \(\textit{liberty}\)). Otherwise, the stone (or group) is captured.

You are given the initial configuration of the board. Then, you are asked \(q\) queries. In each query, you independently flip the color of a stone (change a black stone to a white one, or vice versa) at a given position, while all other stones revert to their original colors. After the flip, compute the number of white stones that are captured (i.e. not alive).

Note: Flipping is done independently for each query on the original board configuration.

The concept of connectivity is defined as follows: Two stones of the same color are directly connected if they are adjacent in one of the four cardinal directions. A stone is in the same connected group as another if there is a sequence of directly connected same-color stones between them. A group is alive if at least one stone in the group has an adjacent empty intersection.

For example, consider the figures below (not to scale):

• In one configuration, both white stones are captured by surrounding black stones, so the output is 2.
• In another configuration, even though one white stone is adjacent to a stone that is not alive, only one white stone is captured, so the output is 1.

inputFormat

The first line contains two integers \(n\) and \(q\) \((1 \leq n \leq 1000, 1 \leq q \leq 10^5)\) representing the size of the board and the number of queries, respectively.

The next \(n\) lines each contain a string of length \(n\) consisting of the characters:

• '.' for an empty intersection,
• 'B' for a black stone, and
• 'W' for a white stone.

Then \(q\) lines follow, each containing two integers \(r\) and \(c\) \((1 \leq r, c \leq n)\) indicating the 1-indexed row and column of the stone to flip. It is guaranteed that the cell \((r,c)\) initially contains a stone (either black or white).

outputFormat

For each query, output a single line containing the number of captured white stones after the specified stone's color is flipped.

A white stone (or a connected group of white stones) is considered captured if none of the stones in the group is adjacent to an empty intersection.

sample

3 2
WB.
BW.
..W
1 1
1 2

0
0