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?

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 \leq n \leq 10^3\) và \(1 \leq q \leq 2 \times 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 \(x_1, y_1, x_2, y_2\) 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

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

Đầu ra

3
1
2