Đếm ô đen

Cho bảng gồm \(n\) hàng, \(m\) cột, mỗi ô là # (ô đen) hoặc . (ô trắng). Có \(q\) câu hỏi, mỗi câu hỏi gồm bốn số \(x_1, y_1, x_2, y_2\): hãy đếm số ô đen trong hình chữ nhật có góc trên trái \((x_1, y_1)\) và góc dưới phải \((x_2, y_2)\) (hàng \(x\), cột \(y\)).

Input

• Dòng đầu tiên chứa ba số nguyên \(n, m, q\) (\(1 \le n, m \le 1000\); \(1 \le q \le 10^5\)).
• \(n\) dòng tiếp theo, mỗi dòng là một xâu độ dài \(m\) gồm # và ..
• \(q\) dòng tiếp theo, mỗi dòng chứa \(x_1, y_1, x_2, y_2\) (\(1 \le x_1 \le x_2 \le n\), \(1 \le y_1 \le y_2 \le m\)).

Output

• In ra \(q\) dòng, mỗi dòng là câu trả lời của một câu hỏi.

Subtask

• \(50\%\) số test: \(n, m, q \le 100\).
• \(50\%\) số test: không có ràng buộc gì thêm.

Sample Input 1

3 4 2
#..#
.##.
#..#
1 1 2 2
1 1 3 4

Sample Output 1

2
6