Farmer John có một tấm toan hình vuông được biểu diễn bằng một lưới \(N \times N\) ô (\(2 \leq N \leq 2000\), \(N\) chẵn). Ông vẽ lên tấm toan theo các bước sau:

1. Đầu tiên, ông chia tấm toan thành bốn góc phần tư bằng nhau, ngăn cách bởi các đường ngang và dọc đi qua tâm tấm toan.
2. Tiếp theo, ông vẽ một bức tranh tuyệt đẹp ở góc phần tư trên bên phải. Mỗi ô trong góc phần tư này có trạng thái được tô (ký hiệu bằng #) hoặc không được tô (ký hiệu bằng .).
3. Cuối cùng, vì rất tự hào về bức tranh của mình, ông phản chiếu nó qua các đường ngang và dọc nói trên sang các góc phần tư còn lại của tấm toan.

Ví dụ, giả sử \(N=8\) và ở bước 2, FJ vẽ bức tranh sau trong góc phần tư trên bên phải:

.#..
.#..
.##.
....

Sau khi phản chiếu qua các đường ngang và dọc sang các góc phần tư khác ở bước 3, tấm toan sẽ trông như sau:

..#..#..
..#..#..
.##..##.
........
........
.##..##.
..#..#..
..#..#..

Tuy nhiên, trong khi FJ đang ngủ, Bessie đột nhập vào kho và đánh cắp tấm toan quý giá của ông. Cô phá hoại toàn bộ tấm toan — xóa màu ở một số ô đã tô và tô thêm nhiều ô khác! Trước khi FJ thức dậy, cô trả tấm toan lại cho ông.

FJ muốn chỉnh sửa tấm toan để nó một lần nữa thỏa mãn điều kiện phản chiếu, tức là nó là kết quả của việc phản chiếu góc phần tư trên bên phải sang từng góc phần tư còn lại. Vì tài nguyên có hạn, ông muốn làm điều này với ít thao tác nhất có thể, trong đó mỗi thao tác là tô một ô hoặc xóa màu khỏi một ô.

Bạn được cho tấm toan sau khi bị Bessie phá hoại, cùng một dãy \(U\) (\(0\le U \leq 10^5\)) cập nhật trên tấm toan; mỗi cập nhật đảo trạng thái của một ô: từ # thành . hoặc ngược lại. Trước mọi cập nhật và sau mỗi cập nhật, hãy in ra số thao tác tối thiểu \(x\) mà FJ cần thực hiện để thỏa mãn điều kiện phản chiếu.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(U\).

\(N\) dòng tiếp theo, mỗi dòng chứa \(N\) ký tự biểu diễn tấm toan sau khi bị Bessie phá hoại. Mỗi ký tự là # hoặc ..

\(U\) dòng sau đó, mỗi dòng chứa hai số nguyên \(r\) và \(c\), với \(1 \leq r,c \leq N\), biểu diễn một cập nhật tại ô ở hàng thứ \(r\) tính từ trên xuống và cột thứ \(c\) tính từ trái sang.

Dữ liệu ra

In ra \(U+1\) dòng biểu diễn \(x\) trước mọi cập nhật và sau mỗi cập nhật.

Ví dụ

4 5
..#.
##.#
####
..##
1 3
2 3
4 3
4 4
4 4

4
3
2
1
0
1

....
####
####
....

....
##.#
####
..##

....
####
####
..##

Phân nhóm

• Dữ liệu 2–3: \(N \le 4\).
• Dữ liệu 4–6: \(U \le 10\).
• Dữ liệu 7–16: Không có ràng buộc bổ sung.

Nguồn

USACO 2025 February Contest, Bronze — Reflection. Tác giả: Chongtian Ma.

https://usaco.org/index.php?page=viewproblem2&cpid=1491