Blogger dili
Benjaminin nəvəsi Brenda, məktəb, dostlar və digər həyat məsələləri haqqında məqalələr paylaşdığı bir bloqa sahibdir. Benjamin, Brenda'nın yazılarını oxumağa çalışdı, lakin onun yazı tərzi səbəbindən oxumaqda çətinlik çəkdi.
Brenda, yazılarında boşluq və durğu işarələrindən istifadə etmir və kiçik-böyük hərfləri qarışıq şəkildə yazır. Məsələn, onun yazılarından biri "PrOgRAMmINgiSgrEAt" kimi görünə bilər. Benjamin bu cür yazılarda "programming", "is" və "great" sözlərini ayırd etməkdə çətinlik çəkir.
Benjamin, bu problemi həll etmək üçün belə bir üsul seçdi: əvvəlcə müəyyən bir t sətirini və maraqlandığı bir bloq yazısını seçəcək; sonra yazının ardıcıl bir alt sətirini seçəcək və t-ni bu alt sətirdə, hərf ölçüsünə həssas olmadan axtaracaq; t-nin alt sətirdəki hər bir meydana gəlməsi üçün hərf ölçüsü uyğunsuzluqlarının sayını hesablayacaq və nəhayət, bu dəyərlər arasında maksimumunu tapacaq. Məsələn, Benjamin "GR"-ni t olaraq seçsə və sonra "PrOgRAM" alt sətirini seçsə, 1 uyğunsuzluğu olan "gR" meydana gəlməsini tapardı. Eyni alt sətir üçün, əgər "r" t olaraq seçilsəydi, 0 uyğunsuzluğu olan "r" və 1 uyğunsuzluğu olan "R" olmaqla iki meydana gəlmə tapardı, beləliklə maksimum uyğunsuzluq sayı 1 olardı.
İşləri daha da çətinləşdirmək üçün Brenda bloqda bir skript daxil etdi ki, bu da alt sətir seçimi ilə işlədikdən sonra seçilmiş hərflərin hamısının ölçüsünü dəyişir. Bu o deməkdir ki, "PrOgRAM" seçildikdən və yuxarıda izah edildiyi kimi davam edildikdən sonra nümunə yazı "pRoGrammINgiSgrEAt" şəklində oxunacaq. Əgər Benjamin ikinci alt sətir olaraq "ammINgi" seçsə, nəticəsini hesabladıqdan sonra yazı "pRoGrAMMinGISgrEAt" şəklində qalacaq, hər iki dəyişiklik yığılaraq.
Sizə Benjaminin seçdiyi t sətiri və orijinal bloq yazısı veriləcək. Sizə həmçinin Benjaminin etdiyi alt sətir seçimlərinin siyahısı veriləcək, etdiyi ardıcıllıqla. Hər seçim üçün, əvvəlki seçimlər tərəfindən edilən bütün hərf ölçüsü dəyişikliklərini nəzərə alaraq, seçilmiş hissədə t-nin meydana gəlmələrinin maksimum hərf ölçüsü uyğunsuzluqlarını hesablamalısınız. Qeyd edin ki, hərf ölçüsünün dəyişməsi hər seçim üçün nəticəni hesabladıqdan sonra baş verir.
Giriş verilənləri
Birinci sətir n (1 ≤ n ≤ 10^5) tam ədədi və ən çox 5 hərfdən ibarət olan boş olmayan t sətirini ehtiva edir, müvafiq olaraq alt sətir seçimlərinin sayını və axtarılacaq sətiri təmsil edir. İkinci sətir ən çox 10^5 hərfdən ibarət olan boş olmayan P sətirini ehtiva edir, Benjaminin seçdiyi bloq yazısının orijinal mətnini göstərir. Yazının mövqeləri soldan sağa doğru ardıcıl tam ədədlərlə nömrələnir, soldakı ən sol mövqe 1 və sağdakı ən sağ mövqe |p| olur. Növbəti n sətirin hər biri l və r (1 ≤ l ≤ r ≤ |p|) tam ədədləri ilə təsvir olunan bir alt sətir seçimini göstərir, bu da alt sətirin l mövqeyində başlayıb r mövqeyində bitdiyini göstərir.
Çıxış verilənləri
n sətir çıxarın, hər biri bir tam ədəd ehtiva edir. i-ci sətirdə, əvvəlki seçimlər tərəfindən edilən bütün hərf ölçüsü dəyişikliklərini nəzərə alaraq, i-ci alt sətir seçimində t-nin meydana gəlmələrinin maksimum hərf ölçüsü uyğunsuzluqlarını yazın; əgər belə bir meydana gəlmə yoxdursa, -1 dəyərini yazın.