Migrated from Lutece 2552 room

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

You are given a matrix with $N$ rows and $M$ colums 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?".

Input

The first line contains three integers $N,M,Q$.

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

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

Output

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

Samples

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

12
8
6
2

Constraints

$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$

Note

Resources

2021 UESTC ICPC Training for Graph