Bạn được cho một lưới \(n \times n\) thể hiện bản đồ của một khu rừng. Mỗi ô vuông có thể trống hoặc chứa một cái cây. Ô phía trên bên trái có tọa độ \((1,1)\), và ô phía dưới bên phải có tọa độ \((n,n)\).

Nhiệm vụ của bạn là xử lí \(q\) truy vấn dưới dạng: có bao nhiêu cây trong một hình chữ nhật đã cho của khu rừng?

Input

• Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(q\): kích thước của khu rừng và số lượng truy vấn.
• Kế tiếp, có \(n\) dòng mô tả khu rừng. Mỗi dòng có \(n\) kí tự: . là một ô trống và * là một cái cây.
• Cuối cùng, có \(q\) dòng mô tả các truy vấn. Mỗi dòng có bốn số nguyên \(y_1, x_1, y_2, x_2\) tương ứng với các góc của một hình chữ nhật.

Constraints

• \(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\)

Output

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

Example

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

3
1
2