Dima və sətirlər
Dima axtarış alqoritmlərini öyrənir və bir sətirin digərinə daxil olmasını tapmağa çalışır. Konkret olaraq, o, t sətirində i indeksindən başlayıb j indeksində bitən alt sətirin s sətiri ilə uyğun gəldiyi indeks cütlərini (i, j) tapmaq istəyir.
Dima bu problemi həll etmək üçün yeni və sürətli bir alqoritm düşünməyə çalışır. Alqoritmin əsas ideyası yalnız bəzi simvolları müqayisə edərək uyğun gələn indeks cütlərinin sayını əhəmiyyətli dərəcədə azaltmaqdır. O, artıq bir neçə müqayisə aparıb və indi bilmək istəyir ki, onun əldə etdiyi məlumatlara zidd olmayan və hələ də cavab olan neçə indeks cütü qalıb.
Unutmayın ki, Dima hələ kiçik bir oğlandır, buna görə də ölçmələrində səhv edə bilər. Əgər giriş məlumatları ziddiyyətlidirsə, 0 çıxarın.
Dima istifadə etdiyi əlifba tam olaraq 10^100 hərfdən ibarətdir.
Giriş verilənləri
Birinci sətir üç tam ədəd n, l_s, l_t (0 ≤ n ≤ 100, 1 ≤ l_s ≤ l_t ≤ 10^9) ehtiva edir. Burada n - aparılmış müqayisələrin sayı, l_s - s sətirinin uzunluğu və l_t - t sətirinin uzunluğudur. Növbəti n sətir hər biri bir müqayisə haqqında məlumat ehtiva edir. Hər sətir i ədədini, 1 ≤ i ≤ l_s, boşluq, "=" və ya "!" simvolu, boşluq və j ədədini, 1 ≤ j ≤ l_t ehtiva edir. Əgər "=" simvolu istifadə olunubsa, onda s_i = t_j, əgər "!" simvolu istifadə olunubsa, onda s_i ≠ t_j.
Çıxış verilənləri
Bir ədəd - Dima'nın sualına cavab.