| Codeforces Round 619 (Div. 2) |
|---|
| Закончено |
Вараврех создал великую компанию и назвал ее Нанософт. Единственная вещь, которую Вараврех еще должен сделать это расположить огромное изображение с эмблемой Нанософта на главное здание этой компании.
Эмблема Нанософта может быть описана как четыре квадрата одинакового размера, объединенных вместе в один большой квадрат. Левый верхний квадрат окрашен в красный цвет, правый верхний квадрат окрашен в зеленый цвет, левый нижний окрашен в желтый цвет и правый нижний окрашен в синий цвет.
Примеры некоторых корректных эмблем:
Примеры некоторых некорректных эмблем:
Вараврех пришел в магазин Адхами с целью купить необходимое изображение. Хотя магазин Адхами очень большой у него было ровно одно изображение, описываемое таблицей с $$$n$$$ строками и $$$m$$$ столбцами. Цвет каждой клетки этой таблицы может быть зеленым (символ 'G'), красным (символ 'R'), желтым (символ 'Y') или синим (символ 'B').
Адхами дал Варавреху $$$q$$$ опций, в каждой опции он дал ему подпрямоугольник этого изображения и сказал ему, что он может вырезать для себя подквадрат этого подпрямоугольника. Чтобы выбрать наилучшую опцию, Вараврех хочет узнать максимальную площадь подквадрата внутри данного подпрямоугольника, который является эмблемой Нанософта. Если таких подквадратов не существует, то ответ равен $$$0$$$.
Вараврех так и не смог выбрать наилучшую опцию сам, поэтому просит вас о помощи. Можете ли вы помочь ему?
В первой строке находится три целых числа $$$n$$$, $$$m$$$ и $$$q$$$ $$$(1 \leq n , m \leq 500, 1 \leq q \leq 3 \cdot 10^{5})$$$ — количество строк, столбцов и количество опций.
Каждая из следующих $$$n$$$ строк содержит строку, содержащую $$$m$$$ символов. В $$$i$$$-й строке $$$j$$$-й символ будет содержать цвет клетки в $$$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)$$$. В этой опции Адхами дает подпрямоугольник изображения с левым верхним углом в клетке $$$(r_1, c_1)$$$ и правым нижним углом в клетке $$$(r_2, c_2)$$$.
Для каждой опции выведите максимальную площадь подквадрата внутри данного подпрямоугольника, который может быть эмблемой Нанософта. Если таких подквадратов не существует, то выведите $$$0$$$.
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
16 4 4 4 0
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
36 4 16 16 16
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
64 0 16 4 16 4 36 0
Картинка для первого теста:
Картинки слева направа соответствуют опциям. Черным обведена граница подпрямоугольника в соответствующей опции, серым обведена граница подквадрата максимального размера, который можно вырезать.
