Cho bảng 2 chiều gồm ~N~ dòng và ~M~ cột, trong đó ~A_{ij}~ nhận một trong hai giá trị là # hoặc .. Trả lời các truy vấn dạng ~(U, L, D, R, K)~ dạng:

• Đếm số điểm ~(i,j)~ sao cho hình vuông con ~K \times K~ có góc trái trên là ~(i,j)~ nằm trọn trong hình chữ nhật con có góc trái trên là ~(U,L)~, và góc phải dưới là ~(D,R)~, và hình vuông con này chỉ chứa toàn dấu '.'. Nói cách khác, ta cần đếm số điểm ~(i,j)~ thoả mãn đồng thời:

  • ~U \le i \le i+K-1 \le D~,

  • ~L \le j \le j+K-1 \le R~,

  • ~A_{uv} =~ '.' ~\forall u \in [i, i+K-1], v \in [j, j+K-1]~.

Input

Dòng đầu tiên chứa ba số nguyên dương ~N~, ~M~ và ~Q~ thể hiện kích thước của bảng và số truy vấn (~1 \le N,M \le 2000~, ~1 \le Q \le 3 \cdot 10^5~).

~N~ dòng tiếp theo, mỗi dòng chứa một xâu kí tự độ dài ~M~. Dữ liệu vào đảm bảo mỗi kí tự trong xâu chỉ nhận một trong hai giá trị là # hoặc ..

~Q~ dòng cuối cùng, mỗi dòng chứa 5 số nguyên ~U~ ~L~ ~D~ ~R~ ~K~ thể hiện một truy vấn (~1 \le U \le D \le N~, ~1 \le L \le R \le M~, ~1 \le K \le 10~).

Output

Với mỗi truy vấn, in ra kết quả của truy vấn đó trên một dòng.

Sample Input 1

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

Sample Output 1

2
0
2
5

Sample Input 2

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

Sample Output 2

15
8
3
2

Notes

Xét test ví dụ đầu tiên:

• Các ô thoả mãn ở truy vấn ~1~: (~1~, ~1~), (~2~, ~2~)

• Các ô thoả mãn ở truy vấn ~3~: (~2~, ~2~), (~2~, ~3~)

• Các ô thoả mãn ở truy vấn ~4~: (~1~, ~1~), (~2~, ~2~), (~2~, ~3~), (~2~, ~4~), (~3~, ~2~)