Đề bài: Cho một lưới có kích cỡ n × 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
|
3 1 2 |
