Bạn được cho một lưới gồm \(n \times 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

Constraints

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

Output

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

Example

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

3
4

.**
*..

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

.**
**.