CF1301E Nanosoft

Warawreh 创办了一家名为 Nanosoft 的伟大公司。他现在唯一要做的事情，就是在公司大楼顶部放置一张包含公司 logo 的大型图片。 Nanosoft 的 logo 可以描述为四个大小相同的正方形拼接成一个更大的正方形。左上角的正方形为红色，右上角为绿色，左下角为黄色，右下角为蓝色。 一些正确的 logo 示例：  一些错误的 logo 示例：  Warawreh 去 Adhami 的商店购买所需的图片。虽然 Adhami 的商店很大，但他只有一张图片，可以描述为 $n$ 行 $m$ 列的网格。图片中每个格子的颜色可以是绿色（用符号 'G' 表示）、红色（'R'）、黄色（'Y'）或蓝色（'B'）。 Adhami 给了 Warawreh $q$ 个选择，每个选择中他会给出图片的一个子矩形，并告诉他可以为他裁剪这个子矩形。为了选择最佳方案，Warawreh 需要知道对于每个选择，在给定的子矩形中，能够作为 Nanosoft logo 的最大子正方形的面积是多少。如果不存在这样的子正方形，答案为 $0$。 Warawreh 自己无法找到最佳方案，于是请求你帮忙。你能帮他吗？

输入的第一行包含三个整数 $n$、$m$ 和 $q$，表示图片的行数、列数和选项数，满足 $1 \leq n, m \leq 500, 1 \leq q \leq 3 \times 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 logo 的最大子正方形的面积。如果不存在这样的子正方形，输出 $0$。

第一个测试点的图片如下：  从左到右的图片分别对应各个选项。选项中的子矩形边界用黑色标记，能够裁剪出的最大正方形的边界用灰色标记。 由 ChatGPT 4.1 翻译