Trong chuyến đi thực địa môn Sinh học, thầy giáo giao cho Nam một tấm bản đồ vệ tinh mô tả một khu rừng nguyên sinh kích thước ~n \times n~. Mỗi ô vuông trên bản đồ hoặc là bãi đất trống, hoặc có một cây cổ thụ đang phát triển. Để tiện ghi chép, các ô được đánh tọa độ với ô góc trên cùng bên trái là ~(1, 1)~ và ô góc dưới cùng bên phải là ~(n, n)~.

Thầy giáo đưa ra liên tiếp ~q~ câu hỏi khảo sát: Mỗi câu hỏi yêu cầu xác định xem có bao nhiêu cây cổ thụ nằm trọn trong một khu vực hình chữ nhật xác định. Vì số lượng truy vấn quá lớn và thời gian trên lớp có hạn, Nam đang rất lúng túng trong việc thống kê. Bạn hãy viết chương trình giúp Nam hoàn thành nhiệm vụ này nhé!

Input

Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~ (~1 \le n \le 1000~, ~1 \le q \le 2 \cdot 10^5~), lần lượt là kích thước cạnh của khu rừng và số lượng truy vấn cần trả lời.

~n~ dòng tiếp theo mô tả khu rừng. Mỗi dòng gồm ~n~ ký tự:

• Ký tự . biểu thị một ô trống.
• Ký tự * biểu thị một ô có chứa cây cổ thụ.

~q~ dòng tiếp theo, mỗi dòng chứa bốn số nguyên ~y_1, x_1, y_2, x_2~ (~1 \le y_1 \le y_2 \le n~, ~1 \le x_1 \le x_2 \le n~) tương ứng với tọa độ góc trên bên trái ~(y_1, x_1)~ và góc dưới bên phải ~(y_2, x_2)~ của khu vực hình chữ nhật cần khảo sát (~y~ là chỉ số hàng, ~x~ là chỉ số cột).

Output

In ra ~q~ dòng, mỗi dòng ghi một số nguyên duy nhất là số lượng cây cổ thụ nằm bên trong hình chữ nhật tương ứng với truy vấn đó.

Sample Input

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

Sample Output

3
1
2