Truy vấn Rừng II

Cho một lưới ô vuông kích thước $n\times n$. Mỗi ô vuông ban đầu là cây (*) hoặc ô trống (.). Bạn cần xử lý $q$ truy vấn thuộc hai loại:

1. Đổi trạng thái ô $(y,x)$: nếu ô đang là cây thì chuyển thành trống, và ngược lại.
2. Đếm số cây trong hình chữ nhật con có góc trên trái $(y_1,x_1)$ và góc dưới phải $(y_2,x_2)$.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $n$ và $q$: kích thước lưới và số truy vấn.

• $n$ dòng tiếp theo, mỗi dòng chứa xâu $n$ ký tự mô tả lưới. Ký tự * là cây, . là ô trống.

• $q$ dòng tiếp theo, mỗi dòng mô tả một truy vấn:

• 1 y x: đổi trạng thái ô $(y,x)$

• 2 y1 x1 y2 x2: đếm số cây trong hình chữ nhật từ $(y_1,x_1)$ đến $(y_2,x_2)$

Dữ liệu ra

Với mỗi truy vấn loại 2, in ra số cây trong hình chữ nhật tương ứng.

Ràng buộc

• $1\le n\le 1000$
• $1\le q\le 2·{10}^5$
• $1\le y\le n$, $1\le x\le n$
• $1\le y_1\le y_2\le n$, $1\le x_1\le x_2\le n$

Ví dụ