Rooms

You are given a matrix with $N$ rows and $M$ columns. Each cell contains one lowercase English letter.

A room is a maximal set of cells that contain the same letter and are connected in 4 directions: up, down, left, and right.

Answer $Q$ queries. Each query gives a rectangular submatrix, and you must count the rooms that are completely or partly inside it.

The first line contains two integers $N$ and $M$. Each of the next $N$ lines contains $M$ lowercase letters. The next line contains the integer $Q$, the number of queries. Each of the following $Q$ lines contains four integers $x_1$, $y_1$, $x_2$, and $y_2$, which describe the rectangle whose diagonally opposite corners are $(x_1, y_1)$ and $(x_2, y_2)$.

Print $Q$ lines. The $i$-th line contains the answer to the $i$-th query.

$1 \le N, M \le 2000$

$1 \le Q \le 5000$

$1 \le x_1, x_2 \le N$

$1 \le y_1, y_2 \le M$