Truy Vấn Rừng 2D

Cho một lưới $n\times n$ gồm các ô trống (.) và cây (*). Hãy trả lời $q$ truy vấn, mỗi truy vấn hỏi có bao nhiêu cây trong hình chữ nhật từ hàng $r_1$, cột $c_1$ đến hàng $r_2$, cột $c_2$ (góc trên-trái đến góc dưới-phải).

Dữ liệu vào

Dòng đầu gồm hai số nguyên $n$ và $q$.

• $n$ dòng tiếp theo, mỗi dòng gồm $n$ ký tự . hoặc *.

• $q$ dòng tiếp theo, mỗi dòng gồm bốn số nguyên $r_1$, $c_1$, $r_2$, $c_2$.

Dữ liệu ra

Với mỗi truy vấn, in số lượng cây trong hình chữ nhật đã cho.

Ràng buộc

• $1\le n\le 1000$
• $1\le q\le 2\times {10}^5$
• $1\le r_1\le r_2\le n$
• $1\le c_1\le c_2\le n$

Ví dụ