Мова блогера
Внучка Бенджаміна, Бренда, веде блог, де публікує статті про школу, друзів та інші життєві питання. Зацікавлений її думками, Бенджамін спробував його прочитати, але швидко зрозумів, що це занадто складно через особливості письма Бренди.
Бренда пише без пробілів та розділових знаків, а також вільно і незвично використовує великі та малі літери. Наприклад, один з її постів виглядає як "PrOgRAMmINgiSgrEAt". Бенджаміну важко розпізнати слова "programming", "is" та "great", коли вони написані таким чином.
Щоб покращити своє розуміння, Бенджамін вирішив зробити наступне: спочатку він вибере певний рядок t та блог-пост, який його цікавить; потім він вибере суміжний підрядок посту і шукатиме t у цьому підрядку, не враховуючи регістр; для кожного входження t у підрядок він підрахує кількість невідповідностей регістру, і нарешті отримає максимальне значення серед усіх цих значень. Наприклад, якщо Бенджамін вибере "GR" як t і потім вибере підрядок "PrOgRAM", він знайде одне входження "gR", для якого кількість невідповідностей регістру дорівнює 1. Для того ж підрядка, якщо вибрати "r" як t, він знайде два входження, "r" з 0 невідповідностями і "R" з 1 невідповідністю, тому максимальна кількість невідповідностей буде 1.
Щоб ускладнити ситуацію, Бренда додала в блог скрипт, який після операції з вибором підрядка змінює регістр усіх вибраних літер. Це означає, що після вибору "PrOgRAM" і виконання описаних вище дій, зразковий пост буде виглядати як "pRoGrammINgiSgrEAt". Якщо Бенджамін вибере "ammINgi" як другий підрядок, після обчислення свого результату пост буде виглядати як "pRoGrAMMinGISgrEAt", накопичуючи обидві зміни регістру.
Вам буде надано рядок t та оригінальний текст блог-посту, обраного Бенджаміном. Вам також буде надано список виборів підрядків, зроблених Бенджаміном, у порядку їх виконання. Вам потрібно обчислити, для кожного вибору, максимальну кількість невідповідностей регістру входжень t у вибраній частині, враховуючи всі зміни регістру, зроблені попередніми виборами. Зверніть увагу, що зміна регістру відбувається після обчислення результату для кожного вибору.
Вхідні дані
Перша строка містить ціле число n (1 ≤ n ≤ 10^5) і непорожній рядок t довжиною не більше 5 літер, що представляють відповідно кількість виборів підрядків та рядок для пошуку. Друга строка містить непорожній рядок P довжиною не більше 10^5 літер, що вказує на оригінальний текст блог-посту. Позиції посту нумеруються послідовними цілими числами зліва направо, де 1 — це крайня ліва позиція, а |p| — крайня права позиція. Кожна з наступних n строк описує вибір підрядка двома цілими числами l та r (1 ≤ l ≤ r ≤ |p|), що вказують, що підрядок починається з позиції l і закінчується позицією r, включно.
Вихідні дані
Виведіть n строк, кожна з яких містить ціле число. У i-й строкі напишіть максимальну кількість невідповідностей регістру входжень t у i-му виборі підрядка, враховуючи всі зміни регістру, зроблені попередніми виборами; якщо такого входження не існує, напишіть значення -1.