题目描述

$Rubyonly$ 最近学会了穿搭，于是他之前的格子衫全都废弃了。

他把这些格子衫裁成了一块 $n\times m$ 的布料，这块布料有 $n\times m$ 个方格。

$Rubyonly$ 的格子衫只有四种颜色。因此，这块布料上颜色也只有四种，每个方格的颜色为黑色，白色，粉色，绿色其中之一。

$Rubyonly$ 觉得直接扔了很可惜，于是他想用这块布料裁出一块正方形的抹布，为了美观，这块抹布必须满足：

是一个正方形，且可以等分为四个正方形，左上角的正方形必须都是黑色，右上角的正方形必须都是白色，左下角的正方形必须都是粉色，右下角的正方形必须都是绿色。

$Rubyonly$ 认为美观的抹布如下：

BW
PG

BBWW
BBWW
PPGG
PPGG

$Rubyonly$ 想裁出很多块不同的抹布，于是，他希望你能帮助他解决 $q$ 个问题。

对于第 $i$ 个问题，他会给你四个正整数 $x_1, y_1, x_2, y_2$，表示布料上的一块矩形区域。你需要告诉他，用这块矩形区域的布料，能够裁出的美观的抹布的最大面积是多少。

输入格式

从文件 shirt.in 中读入数据。

第一行 $3$ 个正整数 $n,m,q$，分别表示布料方格的行数、列数，以及 $Rubyonly$ 的问题个数。

接下来 $n$ 行，第 $i$ 行一个长度为 $m$ 的字符串，表示布料第 $i$ 行方格的颜色序列。

接下来 $q$ 行，每行 $4$ 个正整数 $x_1, y_1, x_2, y_2$，表示询问的矩形区域。

输出格式

输出到文件 shirt.out 中。

输出 $q$ 行，每行 $1$ 个整数表示每次询问的答案。

5 5 3
BWWBW
PGBWW
PGPGG
PPGGG
GPGGG
2 1 3 3
1 1 3 2
1 1 2 3

0
4
4

数据范围

对于全部数据，满足：$1\leq n, m\leq 500$，$1\leq q\leq 3\times 10^5$。

特殊性质：布料中粉色的方格不超过 $100$ 个。