Truy vấn rừng cây (Forest Queries)

Nguồn: CSES

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho một khu rừng hình vuông kích thước $n\times n$. Mỗi ô là:

• * nếu có cây;
• . nếu không có cây.

Bạn cần trả lời $q$ truy vấn hình chữ nhật. Mỗi truy vấn cho hai ô góc $(y_1,x_1)$ và $(y_2,x_2)$, với các hàng từ $y_1$ đến $y_2$ và các cột từ $x_1$ đến $x_2$ đều được tính.

Hãy đếm số cây nằm trong mỗi hình chữ nhật truy vấn.

Input

• Dòng đầu chứa hai số nguyên $n,q$.
• $n$ dòng tiếp theo mô tả khu rừng; mỗi dòng chứa $n$ ký tự . hoặc *.
• Mỗi trong $q$ dòng cuối chứa bốn số nguyên $y_1,x_1,y_2,x_2$.

Output

Với mỗi truy vấn, in trên một dòng số ô chứa cây trong hình chữ nhật tương ứng.

Subtask

Điều kiện chung đã đối chiếu với nguồn:

• $1\le n\le1000$

• $1\le q\le2\cdot10^5$

• Mỗi ô là . hoặc *.

• Tọa độ truy vấn tạo hình chữ nhật hợp lệ.

• Subtask 1 — 20%: $n,q\le20$

• Subtask 2 — 30%: Mọi truy vấn có góc trên-trái là $(1,1)$.

• Subtask 3 — 50%: không có điều kiện bổ sung ngoài các điều kiện chung ở trên.

Ví dụ

Input

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

Output

3
1
2

Giải thích

Khu rừng là

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

• Hình chữ nhật từ $(2,2)$ đến $(3,4)$ chứa $3$ cây.
• Truy vấn $(3,1)$ đến $(3,1)$ chỉ xét một ô và ô đó có cây, nên kết quả là $1$.
• Hình chữ nhật từ $(1,1)$ đến $(2,2)$ chứa hai cây, nên kết quả là $2$.