Đếm số thành phần liên thông

Cho \(1\) bảng có kích thước \(M \times N\) (\(M\) hàng \(N\) cột), mỗi ô của bảng có chứa \(1\) chữ cái tiếng Anh viết thường. Ô giao của hàng \(i\) và cột \(j\) được ký hiệu là ô \((i, j)\). Coi mỗi ô của bảng là một đỉnh của đồ thị, trong đó \(2\) ô có cạnh nối với nhau khi và chỉ khi chúng có chung cạnh và chữ cái được viết trong \(2\) ô đó là giống nhau.

Yêu cầu:

Cho \(Q\) truy vấn, mỗi truy vấn gồm \(4\) số nguyên \(x_{1}, y_{1}, x_{2}, y_{2}\). \((1 \leq x_{1} \leq x_{2} \leq M, 1 \leq y_{1} \leq y_{2} \leq N)\). Nhiệm vụ của bạn là đếm số lượng thành phần liên thông có ít nhất \(1\) đỉnh thuộc hình chữ nhật có góc trái trên là ô \((x_{1}, y_{1})\) và góc phải dưới là ô \((x_{2}, y_{2})\).

Input

Dòng đầu tiên là \(2\) số nguyên dương \(M\), \(N\) \((1 \leq M, N \leq 2000)\).

\(M\) dòng tiếp theo mỗi dòng gồm \(N\) chữ cái tiếng Anh in thường mô tả \(1\) hàng của bảng.

Dòng tiếp theo là số nguyên \(Q\) \((1 \leq Q \leq 5000)\), số lượng truy vấn bạn cần trả lời.

\(Q\) dòng tiếp theo, mỗi dòng chứa \(4\) số nguyên \(x_{1}, y_{1}, x_{2}, y_{2}\) \((1 \leq x_{1} \leq x_{2} \leq M, 1 \leq y_{1} \leq y_{2} \leq N)\) mô tả truy vấn như đã nói ở trên.

Output

In ra \(Q\) đáp án cho \(Q\) truy vấn theo đúng thứ tự được cho trong input, mỗi đáp án in trên một
dòng.

Example

5 6
aabbcc
abbbcc
cbeaed
adeeed
affttz
3
1 1 5 6
2 1 4 5
3 3 5 6

12
8
6