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\) mô tả các dòng 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.

Output

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

Giới hạn

• \(1≤n≤1000\)
• \(1≤q≤2⋅10^5\)
• \(1≤y_1≤y_2≤n\)
• \(1≤x_1≤x_2≤n\)

Ví dụ

Input:

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

Output:

3
1
2