Bạn được cho một lưới gồm \(n\) $ * $ \(n\) ô tượng trưng cho một khu rừng. Mỗi ô có thể là "\(.\)" (Trống) hoặc "$ * $" (Có cây). Bạn được giao \(q\) truy vấn, mỗi truy vấn có thể là 1 trong 2 loại sau đây:

• Loại 1: Có dạng \(1\) \(x\) \(y\), thay đổi trạng thái ô \((x, y)\) từ có cây sang không có cây hoặc ngược lại (chuyển ô \((x, y)\) từ "$ * \(" sang "\).$" hoặc ngược lại)

• Loại 2: Có dạng \(2\) \(x_1\) \(y_1\) \(x_2\) \(y_2\), đếm số ô có cây có trong vùng hình chữ nhật có vị trí góc trái trên là \((x_1, y_1)\) và góc phải dưới là \((x_2, y_2)\)

Input:

• Dòng đầu tiên có 2 số \(n\) và \(q\)
• \(n\) dòng tiếp theo biểu diễn khu rừng. Mỗi dòng có \(n\) kí tự, mỗi kí tự có thể là "\(.\)" hoặc "$ * $"
• \(q\) dòng cuối, mỗi dòng là 1 truy vấn loại 1 hoặc 2.

Output:

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

Constraints:

\(1 ≤ n < 1000\)

\(1 ≤ q ≤ 2 * 10 ^ 5\)

\(1 ≤ x, y ≤ n\)

\(1 ≤ y_1 ≤ y_2 ≤ n\)

\(1 ≤ x_1 ≤ x_2 ≤ n\)

Example(s):

Input:

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

Output:

3
4

Explaination:

Với truy vấn đầu tiên, vùng hình chữ nhật chúng ta đang truy vấn có góc trái trên ở hàng 2, cột 2 và góc phải dưới ở hàng 3, cột 4 có hình dạng như sau:

.**
*..

Với truy vấn thứ 2, chúng ta thay đổi trạng thái của ô nằm ở hàng 3, cột 3 từ "\(.\)" thành "$ * $". Cả khu rừng bây giờ có dạng:

.*..
*.**
***.
****

Với truy vấn thứ 3, vùng hình chữ nhật đó có dạng:

.**
**.