Мова блогера#6582

Мова блогера

1 секунда

64 мегабайти

Дуже складна

Внучка Бенджаміна, Бренда, веде блог, де публікує статті про школу, друзів та інші життєві питання. Зацікавлений її думками, Бенджамін спробував його прочитати, але швидко зрозумів, що це занадто складно через особливості письма Бренди.

Бренда пише без пробілів та розділових знаків, а також вільно і незвично використовує великі та малі літери. Наприклад, один з її постів виглядає як "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 \leq n \leq 1 0^{5})$ (1 \leq n \leq 10^5) і непорожній рядок $t$ довжиною не більше $5$ літер, що представляють відповідно кількість виборів фрагментів та рядок для пошуку. Друга строка містить непорожній рядок $P$ довжиною не більше $1 0^{5}$ 10^5 літер, що вказує на оригінальний текст блог-посту. Позиції посту нумеруються послідовними цілими числами зліва направо, де $1$ — це крайня ліва позиція, а $∣ P ∣$ — крайня права позиція. Кожна з наступних $n$ строк описує вибір фрагмента двома цілими числами $l$ та $r$ $(1 \leq l \leq r \leq ∣ P ∣)$ (1 \leq l \leq r \leq |P|), що вказують, що фрагмент починається з позиції $l$ і закінчується позицією $r$ , включно.

Вихідні дані

Виведіть $n$ строк, кожна з яких містить ціле число. У $i$ -й строкі напишіть максимальну кількість невідповідностей регістру входжень $t$ у $i$ -му виборі фрагмента, враховуючи всі зміни регістру, зроблені попередніми виборами; якщо такого входження не існує, напишіть значення $- 1$ .

Приклади

Приклад 1