Đếm Cây Trong Hình Chữ Nhật

Một khu rừng được biểu diễn bằng lưới vuông gồm $n$ hàng và $n$ cột. Ô có cây được ký hiệu bằng *, còn ô trống được ký hiệu bằng .. Hàng được đánh số từ trên xuống và cột được đánh số từ trái sang phải, đều bắt đầu từ $1$.

Mỗi truy vấn cho hai ô $(y_1,x_1)$ và $(y_2,x_2)$, lần lượt là góc trên-trái và góc dưới-phải của một hình chữ nhật. Cả bốn cạnh của hình chữ nhật đều được tính vào vùng cần xét. Hãy đếm số cây nằm trong mỗi hình chữ nhật.

Input

• Dòng đầu chứa hai số nguyên $n$ và $q$.
• $n$ dòng tiếp theo, mỗi dòng gồm $n$ ký tự . hoặc *, mô tả khu rừng.
• 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 số cây nằm trong hình chữ nhật tương ứng trên một dòng.

Constraints

• $1\le n\le 1000$.
• $1\le q\le 2\cdot 10^5$.
• $1\le y_1\le y_2\le n$.
• $1\le x_1\le x_2\le n$.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n\le 100$ và $q\le 2000$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

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

2
9
3
1
3