Boya
Magni və Mody Kratos ilə döyüşə hazırlaşarkən darıxdılar və rəngləmə ilə əylənməyə qərar verdilər.
Rəngləmə olduqca qeyri-adi bir şəkildə təşkil olunub: n * m ölçülü bir düzbucaqlıdır və nm ədəd vahid kvadratlara bölünmüşdür. Rəngləmənin sətirləri 1-dən n-ə qədər, sütunları isə 1-dən m-ə qədər nömrələnmişdir. (a, b) ilə a nömrəli sətir və b nömrəli sütunun kəsişməsində yerləşən hüceyrəni ifadə edəcəyik.
Əvvəlcə düzbucaqlı şahmat rəngləməsinə malikdir, yəni (a, b) hüceyrəsi ağ rəngdədir, əgər a + b cüt ədəddirsə, əks halda qara rəngdədir.
Mody nizamı çox sevir. O, rəngləmənin sadəliyini, yəni minimum sayda hüceyrəni təkrar rəngləmək lazım olduğunu adlandırır ki, (yəni qara hüceyrəni ağ etmək və əksinə), bundan sonra elə bir tam t ədədi seçmək mümkün olsun ki, (a, b) hüceyrəsi qara olsun, əgər a ≤ t və əks halda ağ olsun. Başqa sözlə, rəngləmənin sadəliyi, elə minimum sayda hüceyrənin rəngini dəyişməkdir ki, bundan sonra m uzunluğunda tərəf boyunca bir xətt çəkmək mümkün olsun və bu xətdən əvvəlki bütün hüceyrələr qara, bu xətdən sonrakılar isə ağ olsun.
Magni nizamı o qədər də sevmir, amma yaradıcılığı sevir. O, vaxtaşırı rəngləmənin bir hüceyrəsini əks rəngə boyayır, yəni əgər hüceyrə qara idisə, onun rəngini ağ edir və əksinə. Hər belə dəyişiklikdən sonra Mody maraqlanır ki, alınan rəngləmənin sadəliyi nə qədərdir. Ümumilikdə Magni q rəngləmə etmişdir və i-ci rəngləmədə o, (a[i], b[i]) hüceyrəsini rəngləmişdir.
Magni hərəkətlərini çox sürətlə etdiyindən, Mody sizdən ona kömək edəcək bir proqram yazmağı xahiş etdi.
Giriş məlumatları
Birinci sətir rəngləmənin ölçüləri olan iki tam ədəd n və m (1 ≤ n ≤ 200000, 1 ≤ m ≤ 10) ehtiva edir. İkinci sətir Magni tərəfindən edilən rəngləmələrin sayı olan tək bir tam ədəd q (1 ≤ q ≤ 200000) ehtiva edir.
Sonrakı q sətirin hər biri a[i] və b[i] (1 ≤ a[i] ≤ n, 1 ≤ b[i] ≤ m) olan iki tam ədəd ehtiva edir - i-ci hərəkətlə rənglənmiş hüceyrənin koordinatları.
Çıxış məlumatları
Magni tərəfindən edilən hər bir hərəkət üçün rəngləmənin sadəliyini çıxış edin.