Внучка Бенджамина Бренда ведет блог, в котором она публикует статьи о школьных друзьях и других вопросах жизни. Заинтригованный мнением внучки, Бенджамин попытался прочитать его, однако очень скоро понял, что это слишком трудно из-за причуды письма Бренды. Бренда пишет без пробелов и знаков пунктуации, и более того, она пользуется заглавными и прописными буквами странным образом. Например, одно из ее сообщений "\textbf{PrOgRAMmINgiSgrEAt}". Бенджамин с трудом узнал слова "\textbf{programming}", "\textbf{is}" и "\textbf{great}", записанные таким образом. To improve his understanding Benjamin decided to do the following: he will first choose a particular string \textbf{t }and a blog post he is interested in; then he will select a contiguous substring of the post and search for \textbf{t }within the substring, in a case-insensitive way; for each occurrence of \textbf{t }within the substring, he will calculate the number of case mismatches, and nally he will obtain the maximum among all these values. For example, if Benjamin chooses "\textbf{GR}" as \textbf{t }and then selects the substring "\textbf{PrOgRAM}", he would nd a single occurrence "\textbf{gR}" for which the number of case mismatches is \textbf{1}. For the same substring, if "\textbf{r}" was chosen as \textbf{t}, he would have found two occurrences, "\textbf{r}" with \textbf{0 }mismatches and "\textbf{R}" with \textbf{1 }mismatch, so the maximum number of mismatches would be \textbf{1}. To complicate things further, Brenda included in the blog a script that, after operating with a substring selection, flips the case of all the selected letters. This means that after selecting "\textbf{PrOgRAM}" and proceeding as explained above, the sample post would read "\textbf{pRoGrammINgiSgrEAt}". If Benjamin selects "\textbf{ammINgi}" as a second substring, after calculating his result the post would be left as "\textbf{pRoGrAMMinGISgrEAt}", accumulating both flips. You will be given the string \textbf{t }and the original text of the blog post chosen by Benjamin. You will also be given a list of substring selections Benjamin made, in the order he made them. You need to calculate, for each selection, the maximum number of case mismatches of the occurrences of \textbf{t }in the selected part, considering all the case flips made by previous selections. Notice that the flipping of the case occurs after calculating the result for each selection. \InputFile The first line contains an integer \textbf{n }(\textbf{1 }≤ \textbf{n }≤ \textbf{10^5}) and a non-empty string \textbf{ t }of at most \textbf{5 }letters, representing respectively the number of substring selections and the string to search for. The second line contains a non-empty string \textbf{P }of at most \textbf{10^5} letters, indicating the original text of the blog post. Positions of the post are numbered with consecutive integers from left to right, being \textbf{1 }the leftmost position and \textbf{|p|} the rightmost position. Each of the next \textbf{n }lines describes a substring selection with two integers \textbf{l }and \textbf{r }(\textbf{1 }≤ \textbf{l }≤ \textbf{r }≤ \textbf{|p|}) indicating that the substring starts at position \textbf{l} and ends at position \textbf{r}, inclusive. \OutputFile Output \textbf{n }lines, each of them containing an integer. In the \textbf{i}-th line write the maximum number of case mismatches of the occurrences of \textbf{t }in the \textbf{i}-th substring selection, considering all the case flips made by previous selections; if no such occurrence exists write the value \textbf{-1}.