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
注意
第一次测试图片:
从左到右的图片对应于选项。选项中子矩形的边界用黑色标记,可切割的最大可能尺寸的子正方形的边界用灰色标记。