Язык блоггера
Внучка Бенджамина, Бренда, ведет блог, где делится своими мыслями о школе, друзьях и других жизненных вопросах. Заинтересовавшись ее мнением, Бенджамин решил прочитать ее записи, но вскоре столкнулся с трудностями из-за необычного стиля письма Бренды.
Бренда пишет без пробелов и знаков препинания, а также произвольно использует строчные и прописные буквы. Например, один из ее постов выглядит как "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.