Mô tả bài toán:

Cho một lưới ~ n \times n ~ đại diện cho bản đồ của một khu rừng. Mỗi ô trong lưới có thể:

• Là một ô trống (ký hiệu là .).
• Chứa một cái cây (ký hiệu là *).

Nhiệm vụ của bạn là xử lý ~ q ~ truy vấn dạng: Có bao nhiêu cây nằm trong một hình chữ nhật được chỉ định trong khu rừng?

Input:

• Dòng đầu tiên chứa hai số nguyên ~ n ~ và ~ q ~: kích thước của khu rừng và số lượng truy vấn.
• Tiếp theo là ~ n ~ dòng mô tả khu rừng, mỗi dòng chứa ~ n ~ ký tự (. hoặc *).
• Sau đó là ~ q ~ dòng, mỗi dòng chứa bốn số nguyên ~ y_1, x_1, y_2, x_2 ~, đại diện cho các góc của hình chữ nhật:
  • Góc trên-trái: ~(y_1, x_1)~.
  • Góc dưới-phải: ~(y_2, x_2)~.

Output:

• In ra số lượng cây trong mỗi hình chữ nhật được chỉ định.

Ràng buộc:

• ~ 1 \leq n \leq 1000 ~
• ~ 1 \leq q \leq 2 \cdot 10^5 ~
• ~ 1 \leq y_1 \leq y_2 \leq n ~
• ~ 1 \leq x_1 \leq x_2 \leq n ~

Ví dụ:

Input:

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

Output:

3
1
2

Giải thích:

1. Truy vấn 1: Hình chữ nhật từ ~(2, 2)~ đến ~(3, 4)~ chứa 3 cây (*).
2. Truy vấn 2: Hình chữ nhật từ ~(3, 1)~ đến ~(3, 1)~ chứa 1 cây (*).
3. Truy vấn 3: Hình chữ nhật từ ~(1, 1)~ đến ~(2, 2)~ chứa 2 cây (*).