The Forest

Điểm số: 1

Giới hạn thời gian: 1s

Giới hạn bộ nhớ: 512 MB

Người đăng: ICTU

Đề bài: Cho một lưới có kích cỡ × n đại diện cho bản đồ của một khu rừng. Mỗi ô là trống hoặc chứa một cây. Hình vuông phía trên cùng bên trái có tọa độ (1,1) và hình vuông phía dưới cùng bên phải có tọa độ (n,n).

Có Q hình chữ nhật được tạo thành từ các ô vuông trên bản đồ ghép lại với nhau. Nhiệm vụ của bạn là trà lời câu hỏi: có bao nhiêu cây bên trong một hình chữ nhật nhất định trong khu rừng?


Đầu vào: 

Dòng đầu tiên có hai số nguyên n và q: kích thước của khu rừng và số lượng hình chữ nhật. 1 <= n <= 10^3, 1 <= q <= 2*10^5

Sau đó, có n dòng miêu tả khu rừng. Mỗi dòng có n ký tự: ( . ) thể hiện là một hình vuông trống và ( * ) là một cái cây.

Cuối cùng, có q dòng mô tả các hình chữ nhật. Mỗi dòng có bốn số nguyên x1, y1, x2, y2 tương ứng với tọa độ của các ô vuông điểm đầu và điểm cuối của hình chữ nhật.


Đầu ra: In ra số cây bên trong mỗi hình chữ nhật.

 

Ví dụ:

 

Đầu vào

Đầu ra

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

 

3

1

2