Олимпиадный тренинг

Задача . E. Нанософт


Задача

Темы: Бинарный поиск дп реализация Структуры данных *2500

Вараврех создал великую компанию и назвал ее Нанософт. Единственная вещь, которую Вараврех еще должен сделать это расположить огромное изображение с эмблемой Нанософта на главное здание этой компании.

Эмблема Нанософта может быть описана как четыре квадрата одинакового размера, объединенных вместе в один большой квадрат. Левый верхний квадрат окрашен в красный цвет, правый верхний квадрат окрашен в зеленый цвет, левый нижний окрашен в желтый цвет и правый нижний окрашен в синий цвет.

Примеры некоторых корректных эмблем:

Примеры некоторых некорректных эмблем:

Вараврех пришел в магазин Адхами с целью купить необходимое изображение. Хотя магазин Адхами очень большой у него было ровно одно изображение, описываемое таблицей с \(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\).

Примечание

Картинка для первого теста:

Картинки слева направа соответствуют опциям. Черным обведена граница подпрямоугольника в соответствующей опции, серым обведена граница подквадрата максимального размера, который можно вырезать.


Примеры
№Входные данныеВыходные данные
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 
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 
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 
64
0
16
4
16
4
36
0

time 2000 ms
memory 512 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет