Benjamin's granddaughter Brenda has a blog where she posts articles about school, friends and other life issues. Intrigued by her opinions, Benjamin tried to read it, but very soon he realized it was too hard to read because of Brenda's writing quirks. Brenda writes without spaces or punctuation marks, and moreover, she uses lower and uppercase letters in a liberal and strange way. For example, one of her posts is "\textbf{PrOgRAMmINgiSgrEAt}". Benjamin has trouble noticing the words "\textbf{programming}", "\textbf{is}" and "\textbf{great}" when they are written in this way. 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}.