Hərfi ilə rəngləndir

Besi yaxınlarda boya dəsti alıb. Kətan n * m ölçülü hüceyrələrdən ibarət düzbucaqlı kimi təsvir olunur, burada sətirlər yuxarıdan aşağıya doğru 1..n ilə, sütunlar isə soldan sağa doğru 1..m ilə nömrələnib. Boyanmış hüceyrə 'A' ilə 'Z' arasında böyük hərflə göstərilir. Başlanğıcda bütün hüceyrələr boyanmamışdır və bir hüceyrə bir dəfədən artıq boyana bilməz.

Besi hər bir hüceyrəni istədiyi rəngə boyamaq istəyir. O, bir toxunuşla bir çox hüceyrəni boyaya bilər, əgər bu hüceyrələr əlaqəli komponent təşkil edirsə, yəni hər hansı bir hüceyrə digərinə qonşu hüceyrələr ardıcıllığı ilə çatdırıla bilər. İki hüceyrə qonşu sayılır, əgər onlar ümumi tərəfə malikdirsə.

Məsələn, 3 * 3 ölçülü kətanı nəzərdən keçirək:

AAB
BBA
BBB

Bu, 4 toxunuşla belə boyana bilər:

...    ..B    AAB    AAB    AAB
... -> ... -> ... -> BB. -> BBA
...    ...    ...    BBB    BBB

Onu 4 toxunuşdan az boyamaq mümkün deyil.

Avanqardist olan Besi yalnız kətanın alt bölgəsini boyamaq istəyir. O, hazırda q namizədi nəzərdən keçirir, hər biri dörd tam ədəd x[1], y[1], x[2], y[2] ilə təmsil olunur. Bu, alt düzbucaqlının x[1]-dən x[2]-yə qədər olan sətirləri və y[1]-dən y[2]-yə qədər olan sütunları əhatə edən bütün hüceyrələrdən ibarət olduğunu bildirir.

Hər bir belə düzbucaqlı üçün bu düzbucaqlının hər bir hüceyrəsini istənilən rəngə boyamaq üçün tələb olunan minimum toxunuş sayını tapın, bu alt düzbucaqlıqdan kənarda olan bütün hüceyrələri boyanmamış saxlayın. Qeyd edək ki, Besi heç nəyi həqiqətən boyamır, buna görə də hər bir namizəd üçün cavablar müstəqildir.

Giriş məlumatları

Girişin ilk sətri n, m (1 ≤ n, m ≤ 1000), q (1 ≤ q ≤ 1000) ədədlərini ehtiva edir.

Növbəti n sətirin hər biri kətanın hər bir sətirinin istənilən rəngini təmsil edən m böyük hərfdən ibarət bir sətir ehtiva edir.

Növbəti q sətirin hər biri dörd tam ədəd x[1], y[1], x[2], y[2] ehtiva edir, alt düzbucaqlını təmsil edir (1 ≤ x[1] ≤ x[2] ≤ n, 1 ≤ y[1] ≤ y[2] ≤ m).

Çıxış məlumatları

Hər bir q sorğu üçün cavabı ayrıca sətirdə çıxarın.

Nümunə

Birinci namizəd - bütün kətan üçün, onu 6 toxunuşla boyamaq olar.

İkinci namizəd - istənilən rənglərlə alt düzbucaqlıdır

ABBA

və 3 toxunuşla boyana bilər. Qeyd edək ki, (3, 5) və (3, 8) hüceyrələri bütün kətanda A rənginə bir toxunuşla boyana bilsə də, göstərilən düzbucaqlıda belə boyana bilməzlər.