Розфарбуй за літерами
Бесі нещодавно отримала набір фарб. Полотно можна уявити як прямокутник розміром n на m клітинок, де рядки пронумеровані від 1 до n зверху вниз, а стовпці — від 1 до m зліва направо. Кожна пофарбована клітинка позначається великою літерою від 'A' до 'Z'. Спочатку всі клітинки не пофарбовані, і кожна клітинка може бути пофарбована лише один раз.
Бесі має бажаний колір для кожної клітинки. Вона може зафарбувати багато клітинок одним дотиком, якщо вони утворюють зв'язну компоненту, тобто будь-яка клітинка цієї множини може бути досягнута з будь-якої іншої через послідовність сусідніх клітинок. Дві клітинки вважаються сусідніми, якщо вони мають спільну сторону.
Наприклад, розглянемо полотно розміром 3 на 3:
AAB BBA BBB
Його можна пофарбувати за 4 дотики таким чином:
... ..B AAB AAB AAB ... -> ... -> ... -> BB. -> BBA ... ... ... BBB BBB
Неможливо пофарбувати його менш ніж за 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 дотиків.
Другий кандидат - підпрямокутник з бажаними кольорами
ABBA
і може бути пофарбований за 3 дотики. Зазначимо, що хоча клітинки (3, 5) і (3, 8) можуть бути пофарбовані в колір A одним дотиком на цілому полотні, вони не можуть бути так пофарбовані в зазначеному прямокутнику.