Ardıcıl#11718
Sizə uzunluğu olan s = s_1 s_2 ... s_n sətir verilib, kiçik ingilis əlifbası hərflərindən ibarətdir.
Bundan əlavə, sizə sətir -ə sorğu verilib. Hər bir i = 1, 2, ..., q üçün, -ci sorğu iki tam ədəd l_i və r_i ilə təqdim olunur və aşağıdakı kimidir:
sətirinin l_i-dən r_i-yə qədər olan simvollarını əhatə edən s_{l_i} s_{l_{i+1}} ... s_{r_i} alt sətirində, eyni kiçik ingilis əlifbası hərfinin ardıcıl iki dəfə təkrarlanması ilə neçə yer mövcuddur? Başqa sözlə, neçə tam ədəd mövcuddur ki, l_i \le p \le r_{i}-1 və s_p = s_{p+1}?
Hər bir sorğu üçün cavabı verin.
Birinci sətirdə iki tam ədəd və q~(1 \le n, q \le 3 \cdot 10^5) verilir.
İkinci sətir uzunluğu olan, kiçik ingilis əlifbası hərflərindən ibarət olan sətiridir.
Növbəti sətirin hər biri sorğu (l_i, r_i), 1 \le l_i, r_i \le n, 1 \le i \le q-ni ehtiva edir.
Hər bir i = 1, 2, ..., q üçün, -ci sorğuya cavab olan sətir verin.
Nümunə 1
Nümunə 2