Nanosoft

Description:

Input:

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)$$$.

Output:

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$$$.

Sample Input:

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

Sample Output:

16
4
4
4
0

Sample Input:

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

Sample Output:

36
4
16
16
16

Sample Input:

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

Sample Output:

64
0
16
4
16
4
36
0

Note:

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.