Rooms

You are given a matrix with $N$ rows and $M$ columns which contains lowercase letters of the English alphabet.

A room is a maximal component of cells which share the same letter and which are connected in $4$ directions: up, down, left, right.

You have to answer queries of the type: "How many rooms are completely or partly included in a given rectangular submatrix?".

The first line contains two integers $N$ and $M$.

Each of the following $N$ lines contains $M$ lowercase letters.

On the following line there is an integer $Q$ indicating the number of queries.

The next $Q$ lines contain $4$ integers $x_1$, $y_2$, $x_2$, $y_2$, denoting a rectangle formed by the diagonally opposite points of coordinates $(x_1,y_1)$ and $(x_2,y_2)$.

You should output $Q$ lines, each containing the answer for a query.

• $1≤N,M≤2\, 000$
• $1≤Q≤5\, 000$
• $1≤x_1,x_2≤N$
• $1≤y_1,y_2≤M$