꿍글리쉬 | cho.sh

문제

꿍은 영타 속도를 높이려고 열심히 연습했고, 이제 순식간에 많은 영어를 입력할 수 있다.

속도만 끌어올린 탓에 꿍이 입력한 영어는 띄어쓰기도 문장부호도 없고 대소문자마저 제멋대로다. 누구도 알아보기 힘든 이 문장을 꿍글리쉬라고 부른다. 예를 들어 programming is great라는 문장은 꿍의 손을 거치면 PrOgRAMmINgiSgrEAt가 된다.

꿍은 자기가 얼마나 복잡한 꿍글리쉬를 만들었는지 알아보려고 다음 과정을 생각했다. 먼저 단어 $T$ 를 하나 고른다. 그 다음 꿍글리쉬 문장의 부분 문자열에서 대소문자를 무시하고 $T$ 가 나타나는 위치를 모두 찾고, 위치마다 $T$ 와 대소문자가 다른 글자가 몇 개인지 센다. 이 값 가운데 가장 큰 값이 그 부분 문자열의 복잡도다. $T$ 가 나타나는 위치는 부분 문자열 안에 완전히 들어 있어야 한다.

$T$ 가 GR이고 PrOgRAMmINgiSgrEAt에서 부분 문자열 PrOgRAM을 고른 경우를 보자. $T$ 는 gR 한 곳에만 나타나고 대소문자가 다른 글자는 하나이므로 복잡도는 1이다. 같은 부분 문자열 PrOgRAM에서 $T$ 를 r로 바꾸면 $T$ 는 r과 R 두 곳에 나타나고 복잡도 후보는 각각 0과 1이므로 복잡도는 1이다.

인성이 안 좋은 꿍은 여러분을 더 화나게 하려고 규칙 하나를 더 붙였다. 한 번의 복잡도를 계산한 다음에는 방금 고른 부분 문자열의 대소문자를 뒤집은 뒤에 다음 복잡도를 계산할 수 있다. 예를 들어 PrOgRAMmINgiSgrEAt에서 PrOgRAM을 골라 복잡도를 계산했다면, 다음 복잡도는 앞 일곱 글자를 뒤집은 pRoGrammINgiSgrEAt에서 계산한다. 이어서 pRoGrammINgiSgrEAt의 부분 문자열 ammINgi로 복잡도를 계산했다면, 그 다음 복잡도는 pRoGrAMMinGISgrEAt에서 계산한다. 복잡도가 -1이 되는 경우에도 대소문자는 똑같이 뒤집는다.

규칙을 만든 꿍조차도 헷갈린다. 여러분이 복잡도를 계산하는 프로그램을 만들자.

꿍이 고른 $T$ 와 꿍글리쉬 문장 하나, 그리고 꿍이 고를 부분 문자열이 순서대로 주어진다. 이 정보로 각 경우의 복잡도를 계산하면 된다.

입력

첫째 줄에 정수 $N$ ( $1 \le N \le 10^5$ )과 단어 $T$ 가 공백을 사이에 두고 주어진다. $N$ 은 부분 문자열을 고르는 횟수이고, $T$ 의 길이는 최대 5이다.

둘째 줄에 공백이 없는 꿍글리쉬 문장 $P$ 가 주어진다. $P$ 의 길이는 최대 $10^5$ 이다.

이어지는 $N$ 개의 줄에 두 정수 $L$ , $R$ ( $1 \le L \le R \le |P|$ )이 주어진다. $P$ 의 $L$ 번째부터 $R$ 번째까지의 부분 문자열을 골라 복잡도를 계산한다는 뜻이다. 문장의 가장 왼쪽 문자가 1번째 문자이고, 가장 오른쪽 문자가 $|P|$ 번째 문자다.

$T$ 와 $P$ 는 영어 대문자와 소문자로만 이루어져 있다.

출력

$N$ 개의 줄에 정수 하나씩을 출력한다. $i$ 번째 줄에는 $i$ 번째로 고른 부분 문자열의 복잡도를 출력한다. 대소문자를 무시했을 때 $T$ 가 그 부분 문자열 안에 한 번도 나타나지 않으면 -1을 출력한다.

힌트

$T$ 가 gR이고 처음 꿍글리쉬 문장이 PrOgRAMmINgiSgrEAt일 때, 구간 (1, 7), (4, 18), (6, 14)를 차례로 고르면 다음과 같이 진행된다.

1번째부터 7번째까지의 부분 문자열은 PrOgRAM이고 복잡도 후보는 0 하나다. 계산이 끝나면 이 구간의 대소문자가 뒤집혀 문장이 pRoGrammINgiSgrEAt로 바뀐다.

4번째부터 18번째까지의 부분 문자열은 GrammINgiSgrEAt이고 복잡도 후보는 2와 1이다. 계산이 끝나면 문장이 pRogRAMMinGIsGReaT로 바뀐다.

6번째부터 14번째까지의 부분 문자열은 AMMinGIsG이고 복잡도 후보가 하나도 없다.