Domino trên lưới

Cho một lưới gồm $h$ hàng và $w$ cột. Mỗi ô của lưới hoặc trống (ký hiệu là ký tự .) hoặc bị cấm (ký hiệu là ký tự #). Các hàng được đánh số từ $1$ đến $h$ từ trên xuống dưới, các cột được đánh số từ $1$ đến $w$ từ trái sang phải.

Một quân domino chiếm đúng hai ô kề nhau, hoặc nằm trong cùng một hàng (kề nhau theo chiều ngang) hoặc nằm trong cùng một cột (kề nhau theo chiều dọc). Một quân domino chỉ có thể được đặt nếu cả hai ô mà nó chiếm đều trống và đều nằm trong lưới.

Cho $q$ truy vấn. Mỗi truy vấn gồm bốn số nguyên $r_1,c_1,r_2,c_2$ mô tả một hình chữ nhật con với ô trái-trên là $(r_1,c_1)$ và ô phải-dưới là $(r_2,c_2)$. Với mỗi truy vấn, hãy đếm số cách đặt một quân domino sao cho cả hai ô mà nó chiếm đều nằm hoàn toàn bên trong hình chữ nhật con này.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $h$ và $w$.
• $h$ dòng tiếp theo, mỗi dòng chứa một xâu độ dài $w$ gồm các ký tự . và # mô tả lưới.
• Dòng tiếp theo chứa một số nguyên $q$ — số truy vấn.
• Mỗi dòng trong $q$ dòng tiếp theo chứa bốn số nguyên $r_{1i},c_{1i},r_{2i},c_{2i}$ mô tả truy vấn thứ $i$.

Dữ liệu ra

In ra $q$ dòng, dòng thứ $i$ là số cách đặt một quân domino trong hình chữ nhật con của truy vấn thứ $i$.

Ràng buộc

• $1\le h,w\le 500$
• $1\le q\le 100000$
• $1\le r_{1i}\le r_{2i}\le h$
• $1\le c_{1i}\le c_{2i}\le w$

Ví dụ