Bài toán tiền xử lý trên lưới: cho bảng ~N\times M~ gồm ô trống '.' và ô chặn '#'. Với mỗi truy vấn hình chữ nhật con xác định bởi ~[x_1..x_2]\times[y_1..y_2]~, hãy đếm số cách đặt domino kích thước ~1\times 2~ (nằm ngang hoặc dọc) mà hoàn toàn nằm trong hình chữ nhật và phủ lên hai ô trống liền kề.

Yêu cầu

Với mỗi truy vấn ~\big(x_1,y_1,x_2,y_2\big)~, tính số lượng domino có thể đặt:

• Domino nằm ngang phủ ~\big(i,j\big)~ và ~\big(i,j+1\big)~ với cả hai ô là '.' và ~x_1\le i\le x_2~, ~y_1\le j\le y_2-1~.
• Domino nằm dọc phủ ~\big(i,j\big)~ và ~\big(i+1,j\big)~ với cả hai ô là '.' và ~x_1\le i\le x_2-1~, ~y_1\le j\le y_2~.

Dữ liệu

• Dòng đầu: ba số nguyên dương ~N~, ~M~, ~Q~ ~(1\le N,M\le 10^3,\ 1\le Q\le 10^5)~.
• ~N~ dòng tiếp theo: mỗi dòng là một chuỗi dài ~M~ gồm ký tự '.' hoặc '#', biểu diễn bảng.
• ~Q~ dòng cuối: mỗi dòng chứa bốn số nguyên ~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)~.

Kết quả

• In ~Q~ dòng, dòng thứ ~i~ là câu trả lời cho truy vấn thứ ~i~.

Ví dụ

Ví dụ 1

Input

9 23 5
.......................
..........#............
.........#.............
..####.#..#.#..#.####..
..#..#.#..#.##.#.#.....
.###.#.#..#.#.##.#.###.
..#..#.#..#.#..#.#..#..
..####.####.#..#.####..
.......................
1 1 9 23
2 2 8 22
3 3 7 21
4 4 6 20
5 5 5 19

Output

205
106
54
19
1

Ví dụ 2

Input

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

Output

10
1
3

Giải thích

Ví dụ 2

Bảng:

..#.
....
#...

• Truy vấn ~[1,1]\times[1,4]~: đếm tất cả cặp ô trống kề nhau (ngang + dọc) trong toàn bảng, được ~10~.
• Truy vấn ~[2,1]\times[3,2]~: chỉ có một domino dọc ở cột ~2~ (hàng ~2\to3~).
• Truy vấn ~[1,3]\times[3,4]~: trong phần bên phải, có ~3~ cách đặt (2 ngang, 1 dọc).

Gợi ý (Có thể đúng hoặc sai)

• 100% số điểm cho lời giải ~\mathcal{O}(NM + Q)~ với tiền xử lý hai mảng đánh dấu:
  • ~H[i,j]=1~ nếu ~grid[i,j]=grid[i,j+1]='.'~ (ô ngang hợp lệ), xét ~1\le i\le N~, ~1\le j\le M-1~.
  • ~V[i,j]=1~ nếu ~grid[i,j]=grid[i+1,j]='.'~ (ô dọc hợp lệ), xét ~1\le i\le N-1~, ~1\le j\le M~.
  • Tính tổng tích luỹ 2D cho ~H~ và ~V~: lần lượt ~\mathrm{prefH}~, ~\mathrm{prefV}~.
• Trả lời truy vấn hình chữ nhật ~[x_1..x_2]\times[y_1..y_2]~ bằng:
  • Số domino ngang: tổng ~H~ trên dải ~i\in[x_1..x_2]~, ~j\in[y_1..y_2-1]~ (nếu ~y_1<y_2~, ngược lại bằng ~0~).</li>
  • Số domino dọc: tổng ~V~ trên dải ~i\in[x_1..x_2-1]~, ~j\in[y_1..y_2]~ (nếu ~x_1<x_2~, ngược lại bằng ~0~).</li>
  • Kết quả là tổng hai giá trị trên.
• Biên: khi ~N=1~ hoặc ~M=1~, chỉ có một loại domino khả dĩ; xử lý bằng các điều kiện biên ở bước truy vấn. Sử dụng I/O nhanh để đáp ứng ~Q\le 10^5~.