Dima və sətirlər#2932
Dima sətirlərin daxilində alt sətirlərin tapılması üçün alqoritmləri öyrənir. Xüsusilə, o, elə bütün indeks cütlərini tapmaq istəyir ki, sətirinin -ci indeksindən başlayıb -ci indeksində bitən alt sətiri sətirinə uyğun olsun.
Dima bu problemi həll etmək üçün yeni və sürətli bir alqoritm kəşf etməyə çalışır. Əsas ideya yalnız müəyyən simvolları müqayisə etməkdir və bu, mümkün indeks cütlərinin sayını xeyli azaldır. O artıq bir neçə müqayisə aparıb və indi bilmək istəyir ki, topladığı məlumatlara zidd olmayan, hələ də mümkün olan neçə indeks cütü var.
Unutmayın ki, Dima hələ cavandır, ona görə də o, ölçmələrində səhvlər edə bilər. Əgər daxil olan məlumatlar ziddiyyətlidirsə, 0 cavabını verin.
Dima tam olaraq 10^{100} hərfdən ibarət əlifbadan istifadə edir.
Birinci sətirdə üç tam ədəd verilir: , l_s, l_t (0 \leq n \leq 100, 1 \leq l_s \leq l_t \leq 10^9), burada aparılmış müqayisələrin sayıdır, l_s sətirinin uzunluğu, l_t isə sətirinin uzunluğudur. Növbəti sətirin hər birində bir müqayisə təsvir edilir. Hər sətirdə (1 \leq i \leq l_s), boşluq, "" və ya "" simvolu, daha bir boşluq və (1 \leq j \leq l_t) ədədi verilir. Əgər "" simvolu qeyd olunubsa, s_i = t_j tələb olunur; əgər "" simvolu verilibsə, s_i \neq t_j tələb olunur.
Bir ədəd çap edin — Dima'nın sualına cavab.
Nümunə 1