Беси недавно получила набор красок. Холст может быть представлен как n * m прямоугольник из ячеек, где строки пронумерованы 1..n сверху вниз, а столбцы пронумерованы 1..m слева направо. Покрашенная ячейка представляется большой буквой от 'A' до 'Z'. Изначально все ячейки не раскрашены, и ячейка не может краситься более одного раза.
У Беси есть желаемый цвет для каждой ячейки. Она может красить множество ячеек одним касанием, если это множество образуем связную компоненту, то есть что любая её ячейка достижима из любой другой через последовательность соседних ячеек. Две ячейки называются соседними, если они имеют общую сторону.
Например, рассмотрим холст 3 * 3:
Он может быть раскрашен за 4 касания так:
Невозможно его раскрасить менее чем за 4 касания.
Будучи авангардисткой, Беси намерена покрасить только подрегион холста. Сейчас она рассматривает q кандидатов, каждый из которых представляется четырьмя целыми числами x[1]
, y[1]
, x[2]
, y[2]
. Это означает, подпрямоугольник состоит из всех ячеек со строками в диапазоне от x[1]
до x[2]
включительно, и колонками в диапазоне от y[1]
до y[2]
включительно.
Для каждого такого прямоугольника какое требуется минимальное количество касаний, чтобы раскрасить каждую из ячеек этого прямоугольника желаемым цветом, оставляя не закрашенными все ячейки вне этого подпрямоугольника. Заметим, Беси ничего не красит реально, поэтому ответы для каждого кандидата независимы.
Первая строка ввода содержит n, m (1 ≤ n, m ≤ 1000), q (1 ≤ q ≤ 1000).
Каждая из последующих n строк содержит строку из m больших букв, представляющих желаемый цвет каждой строки холста.
Каждая из следующих q строк содержит четыре целых числа x[1]
, y[1]
, x[2]
, y[2]
, представляющих подпрямоугольник (1 ≤ x[1]
≤ x[2]
≤ n, 1 ≤ y[1]
≤ y[2]
≤ m).
Для каждого из q запросов выведите ответ в отдельной строке.
Первый кандидат - на весь холст, его можно раскрасить за 6 касаний.
Второй кандидат - подпрямоугольник с желаемыми цветами
и может быть раскрашен за 3 касания. Заметим, что хотя ячейки (3, 5) и (3, 8) могут быть раскрашены в цвет A одним касанием на целом холсте, они не могут быть так раскрашены в указанном прямоугольнике.