Symmetric Canvas Restoration

Farmer John has a square canvas represented by an \(N \times N\) grid (\(2 \le N \le 2000\), \(N\) is even). Initially, he partitions the canvas into four equal quadrants by drawing horizontal and vertical lines through its center. He then creates a beautiful drawing in the top‐right quadrant, where each cell is either painted (#) or unpainted (.). Proud of his work, he reflects the drawing over the center lines to fill the entire canvas.

Unfortunately, while FJ was asleep, Bessie tampered with the canvas by removing paint from some painted cells and adding paint to some unpainted cells. Now FJ wishes to restore the canvas so that it can be obtained by reflecting the top‐right quadrant. In other words, the restored canvas must satisfy the following symmetry: for every group of four cells that are symmetric with respect to the center lines, all cells must have the same state (either all painted or all unpainted).

Formally, consider a cell with coordinates \((i,j)\) (with \(0 \le i,j < N\)). For each group of four cells: \[ \{(i, j),\,(i, N-1-j),\,(N-1-i, j),\,(N-1-i, N-1-j)\} \] (where the group is considered exactly once), let \(c\) be the number of painted cells (denoted by #). The cost to fix this group is \[ \min(c, 4-c)\,. \] The answer is the sum of the costs of all groups, which represents the minimum number of cell toggles required to restore the symmetry.

You are given the current state of the canvas followed by \(U\) update operations. Each update toggles the state of a single cell (from # to . or vice versa). Compute and output the required minimum number of operations initially and after each update.

inputFormat

The first line contains two integers \(N\) and \(U\) (number of updates). \(N\) is even and satisfies \(2 \le N \le 2000\), and \(0 \le U \le 10^5\).

The next \(N\) lines each contain a string of length \(N\) consisting of characters '#' and '.'. These represent the current state of the canvas.

Each of the following \(U\) lines contains two integers \(r\) and \(c\) (0-indexed) indicating the cell to toggle.

outputFormat

Output \(U+1\) lines. The first line is the minimum number of toggle operations required to restore the canvas before any updates. Each of the following \(U\) lines should contain the answer after the corresponding update.

sample

2 1
#.
.#
0 1

2
1