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