← 返回题目列表

Codeforces · 1301/E

E. 纳米软件

中文机器翻译题面 查看原题

Warawreh 创建了一家名为 Nanosoft 的伟大公司。 Warawreh 唯一要做的就是在公司大楼顶部放置一张包含其徽标的大图片。

Nanosoft的标志可以形容为四个相同大小的方块合并成一个大方块。左上方块为红色,右上方块为绿色,左下方块为黄色,右下方块为蓝色。

一些正确徽标的示例:

一些不正确徽标的示例:

Warawreh 前往 Adhami 的商店购买所需的图片。尽管 Adhami 的商店很大,但他只有一张图片,可以将其描述为由 $$$n$$$ 行和 $$$m$$$ 列组成的网格。图片中每个单元格的颜色将为绿色(符号“G”)、红色(符号“R”)、黄色(符号“Y”)或蓝色(符号“B”)。

Adhami 给了 Warawreh $$$q$$$ 选项,在每个选项中他都给了他一张图片中的一个子矩形,并告诉他可以为他剪下那个子矩形。为了选择最佳选项,Warawreh 需要知道每个选项的给定子矩形内可以作为 Nanosoft 徽标的子正方形的最大面积。如果不存在这样的子方格,则答案为$$$0$$$。

Warawreh 自己找不到最好的选择,所以他向你寻求帮助,你能帮助他吗?

输入

输入的第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$q$$$ $$$(1 \leq n , m \leq 500, 1 \leq q \leq 3 \cdot 10^{5})$$$ — 行数、列数和选项数。

对于接下来的 $$$n$$$ 行,每行将包含 $$$m$$$ 个字符。在第 $$$i$$$ 行中,第 $$$j$$$ 字符将包含 Adhami 图片的第 $$$i$$$ 行和第 $$$j$$$ 列的单元格颜色。每个单元格的颜色将为以下之一:{'G','Y','R','B'}。

对于接下来的 $$$q$$$ 行,输入将包含四个整数 $$$r_1$$$、$$$c_1$$$、$$$r_2$$$ 和 $$$c_2$$$ $$$(1 \leq r_1 \leq r_2 \leq n, 1 \leq c_1 \leq c_2 \leq m)$$$。在该选项中,Adhami 向 Warawreh 提供了图片的子矩形,其左上角位于单元格 $$$(r_1, c_1)$$$ 中,右下角位于单元格 $$$(r_2, c_2)$$$ 中。

输出

对于每个选项,打印给定子矩形内子正方形的最大面积,这可以是 NanoSoft 徽标。如果没有这样的子方块,则打印$$$0$$$。

示例

输入 #1

5 5 5
RRGGB
RRGGY
YYBBG
YYBBR
RBBRG
1 1 5 5
2 2 5 5
2 2 3 3
1 1 3 5
4 4 5 5

输出 #1

16
4
4
4
0

输入 #2

6 10 5
RRRGGGRRGG
RRRGGGRRGG
RRRGGGYYBB
YYYBBBYYBB
YYYBBBRGRG
YYYBBBYBYB
1 1 6 10
1 3 3 10
2 2 6 6
1 7 6 10
2 1 5 10

输出 #2

36
4
16
16
16

输入 #3

8 8 8
RRRRGGGG
RRRRGGGG
RRRRGGGG
RRRRGGGG
YYYYBBBB
YYYYBBBB
YYYYBBBB
YYYYBBBB
1 1 8 8
5 2 5 7
3 1 8 6
2 3 5 8
1 2 6 8
2 1 5 5
2 1 7 7
6 5 7 5

输出 #3

64
0
16
4
16
4
36
0

注意

第一次测试图片:

从左到右的图片对应于选项。选项中子矩形的边界用黑色标记,可切割的最大可能尺寸的子正方形的边界用灰色标记。