CF1301E.Nanosoft

Warawreh created a great company called Nanosoft. The only thing that Warawreh still has to do is to place a large picture containing its logo on top of the company's building.

The logo of Nanosoft can be described as four squares of the same size merged together into one large square. The top left square is colored with red, the top right square is colored with green, the bottom left square is colored with yellow and the bottom right square is colored with blue.

An Example of some correct logos:

An Example of some incorrect logos:

Warawreh went to Adhami's store in order to buy the needed picture. Although Adhami's store is very large he has only one picture that can be described as a grid of $n$ rows and $m$ columns. The color of every cell in the picture will be green (the symbol 'G'), red (the symbol 'R'), yellow (the symbol 'Y') or blue (the symbol 'B').

Adhami gave Warawreh $q$ options, in every option he gave him a sub-rectangle from that picture and told him that he can cut that sub-rectangle for him. To choose the best option, Warawreh needs to know for every option the maximum area of sub-square inside the given sub-rectangle that can be a Nanosoft logo. If there are no such sub-squares, the answer is $0$.

Warawreh couldn't find the best option himself so he asked you for help, can you help him?

瓦拉维赫创立了一家名为“纳米软件”（Nanosoft）的优秀公司。目前，他唯一尚未完成的任务就是在公司大楼顶部安装一幅印有公司标志的大幅图像。

纳米软件的标志可描述为：四个大小完全相同的正方形拼接成一个更大的正方形。其中，左上角正方形为红色，右上角正方形为绿色，左下角正方形为黄色，右下角正方形为蓝色。

一些正确标志的示例：

一些错误标志的示例：

瓦拉维赫前往阿德哈米的商店购买所需的图像。尽管阿德哈米的商店规模庞大，但他店内仅有一幅图像，该图像可表示为一个 $n$ 行 $m$ 列的网格。图像中每个单元格的颜色为绿色（字符 'G'）、红色（字符 'R'）、黄色（字符 'Y'）或蓝色（字符 'B'）。

阿德哈米向瓦拉维赫提供了 $q$ 个选项；在每个选项中，他都给出该图像的一个子矩形区域，并告知瓦拉维赫可以将该子矩形裁剪下来。为了选出最优选项，瓦拉维赫需要对每个选项计算：在给定子矩形内，能构成纳米软件标志的最大子正方形的面积。若不存在这样的子正方形，则答案为 $0$。

瓦拉维赫无法自行找出最优选项，因此向你求助——你能帮他解决这个问题吗？

The first line of input contains three integers $n$, $m$ and $q$ $(1 \leq n , m \leq 500, 1 \leq q \leq 3 \cdot 10^{5})$ — the number of row, the number columns and the number of options.

For the next $n$ lines, every line will contain $m$ characters. In the $i$-th line the $j$-th character will contain the color of the cell at the $i$-th row and $j$-th column of the Adhami's picture. The color of every cell will be one of these: {'G','Y','R','B'}.

For the next $q$ lines, the input will contain four integers $r_1$, $c_1$, $r_2$ and $c_2$ $(1 \leq r_1 \leq r_2 \leq n, 1 \leq c_1 \leq c_2 \leq m)$. In that option, Adhami gave to Warawreh a sub-rectangle of the picture with the upper-left corner in the cell $(r_1, c_1)$ and with the bottom-right corner in the cell $(r_2, c_2)$.

输入的第一行包含三个整数 $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)$。

For every option print the maximum area of sub-square inside the given sub-rectangle, which can be a NanoSoft Logo. If there are no such sub-squares, print $0$.

对于每个选项，输出给定子矩形内可构成 NanoSoft 标志的最大子正方形的面积；若不存在这样的子正方形，则输出 $0$。

Picture for the first test:

The pictures from the left to the right corresponds to the options. The border of the sub-rectangle in the option is marked with black, the border of the sub-square with the maximal possible size, that can be cut is marked with gray.

第一个测试的图片：

从左到右的图片分别对应各个选项。选项中子矩形的边界用黑色标出，可被裁剪出的最大可能尺寸的子正方形的边界用灰色标出。