Беси недавно получила набор красок. Холст может быть представлен как
\(N \times M\) прямоугольник из ячеек, где строки пронумерованы \(1\ldots N\)
сверху вниз, а столбцы пронумерованы \(1\ldots M\) слева направо (\(1\le N,M\le 1000\)).
Покрашенная ячейка представляется большой буквой от 'A' до 'Z'.
Изначально все ячейки не раскрашены, и ячейка не может краситься более одного раза.
У беси есть желаемый цвет для каждой ячейки. Она может красить множество ячеек
одним касанием, если это множество образуем связную компоненту, то есть что любая
её ячейка достижима из любой другой через последовательность соседних ячеек.
Две ячейки называются соседними, если они имеют общую сторону.
Например, рассмотрим холст \(3\times 3\)
AAB
BBA
BBB
Он может быть раскрашен за 4 касания так:
... ..B AAB AAB AAB
... -> ... -> ... -> BB. -> BBA
... ... ... BBB BBB
Невозможно его раскрасить менее чем за 4 касания.
Будучи авангардисткой, Беси намерена покрасить только подрегион холста.
Сейчас она рассматривает \(Q\) кандидатов (\(1\le Q\le 1000\)), каждый из которых
представляется четырьмя целыми числами \(x_1\), \(y_1\), \(x_2\), \(y_2.\)
Это означает, подпрямоугольник состоит из всех ячеек со строками в диапазоне
от \(x_1\) до \(x_2\) включительно, и колонками в диапазоне от \(y_1\) до \(y_2\)
включительно.
Для каждого такого прямоугольника какое требуется минимальное количество
касаний, чтобы раскрасить каждую из ячеек этого прямоугольника желаемым цветом,
оставляя не закрашенными все ячейки вне этого подпрямоугольника. Заметим,
Беси ничего не красит реально, поэтому ответы для каждого кандидата независимы.
Замечание: Время на тест в этой задач ена 50% выше чем по умолчанию,
а ограничения оп памяти 512 Мбт - в два раза больше чем по умолчанию.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка ввода содержит
\(N\),
\(M\),
\(Q\).
Каждая из последующих \(N\) строк содержит строку из \(M\) больших букв,
представляющих желаемый цвет каждой строки холста.
Каждая из следующих \(Q\) строк содержит четыре разделённых одиночными пробелами
целых числа \(x_1,y_1,x_2,y_2\), представляющих подпрямоугольник
(\(1\le x_1\le x_2\le N\), \(1\le y_1\le y_2\le M\)).
ФОРМАТ ВЫВОДА (на экран / stdout):
Для каждого из \(Q\) запросов выведите ответ в отдельной строке.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 8 9
ABBAAAAA
ABAAAABA
CAADABBA
AAAAAAAA
1 1 4 8
3 5 3 8
1 3 2 4
1 4 2 5
1 1 3 3
4 4 4 4
2 6 4 8
3 5 4 6
1 6 3 8
|
6
3
2
1
4
1
3
2
2
|