Mô tả bài toán: Xử lý bản đồ rừng

Bạn được cung cấp một bản đồ rừng kích thước ~n \times n~, trong đó mỗi ô là một ô trống hoặc có một cái cây. Nhiệm vụ của bạn là xử lý ~q~ truy vấn thuộc hai loại sau:

1. Thay đổi trạng thái của một ô: Biến ô trống thành ô có cây, hoặc ngược lại.
2. Đếm số cây trong một hình chữ nhật: Đếm số lượng cây trong hình chữ nhật có góc trên bên trái là ~(y_1, x_1)~ và góc dưới bên phải là ~(y_2, x_2)~.

Input:

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~: kích thước rừng và số lượng truy vấn.
• Sau đó có ~n~ dòng, mỗi dòng có ~n~ ký tự:
  • .: ô trống.
  • *: ô có cây.
• Tiếp theo là ~q~ dòng, mô tả các truy vấn:
  • 1 y x: Thay đổi trạng thái của ô tại ~(y, x)~.
  • 2 y_1 x_1 y_2 x_2: Đếm số lượng cây trong hình chữ nhật có góc trên bên trái là ~(y_1, x_1)~ và góc dưới bên phải là ~(y_2, x_2)~.

Output:

• Với mỗi truy vấn loại 2, in ra số lượng cây trong hình chữ nhật được yêu cầu.

Ràng buộc:

• ~1 \leq n \leq 1000~
• ~1 \leq q \leq 2 \cdot 10^5~
• ~1 \leq y, x, y_1, y_2, x_1, x_2 \leq n~

Ví dụ:

Input:

4 3
.*..
*.**
**..
****
2 2 2 3 4
1 3 3
2 2 2 3 4

Output:

3
4

Giải thích:

1. Truy vấn 2 2 2 3 4: Đếm số cây trong hình chữ nhật từ ~(2, 2)~ đến ~(3, 4)~. Kết quả là 3.
2. Truy vấn 1 3 3: Thay đổi trạng thái ô ~(3, 3)~ từ cây thành ô trống.
3. Truy vấn 2 2 2 3 4: Đếm lại số cây, kết quả là 4.