Classic Quotation

온라인 채팅을 하다 보면 누군가 한 말을 저장해 그의 명언을 만들 수 있다. Little Q도 그렇게 한다. 게다가 그는 원래 단어까지 바꿀 수 있다. 형식적으로, 누군가 길이 $n$인 문자열 $S$를 말했다고 하자. Little Q는 $S$의 연속 부분 문자열(비어 있을 수도 있음)을 하나 골라 지우고, 남은 두 부분을 이어 붙여 새 문자열 $S'$을 얻는다. 예를 들어 문자열 "I am not SB"에서 "not "를 지우면 새 문자열 $S'$은 "I am SB"가 된다.

이런 일을 여러 번 한 끝에 Little Q는 문자열 $T$가 $S'$의 연속 부분 문자열로 매우 자주 나타난다는 것을 알게 되었다.

이제 문자열 $S$와 $T$가 주어지고 Little Q에게 $k$개의 질의가 있다. 각 질의는 다음과 같은 형식이다. $L$과 $R$이 주어지면 Little Q는 어떤 부분 문자열을 지워 남은 두 부분이 $S[1..i]$와 $S[j..n]$이 되도록 한다. 여기서 정수 쌍 $(i, j)$는 $1 \leq i \leq L$이고 $R \leq j \leq n$인 모든 쌍 중에서 같은 확률로 선택된다. 결과 문자열에서 $T$가 나타나는 횟수의 기댓값 $E$를 구하고 $E \cdot L \cdot (n - R + 1)$의 값을 출력하라.

$T$가 겹쳐서 나타나는 경우도 모두 세야 한다. 질의들은 서로 독립적이다. 문자열 $S$는 실제로 $S'$으로 변하지 않으며 모든 질의에서 같다.

입력의 첫 줄에는 $S$의 길이, $T$의 길이, 질의의 수를 나타내는 세 정수 $n$, $m$, $k$가 주어진다($1 \leq n \leq 5 \cdot 10^4$, $1 \le m \leq 100$, $1 \le k \le 5 \cdot 10^4$).

다음 줄에는 $n$개의 소문자 영어 알파벳으로 이루어진 문자열 $S$가 주어진다. 그다음 줄에는 $m$개의 소문자 영어 알파벳으로 이루어진 문자열 $T$가 주어진다. 남은 $k$개의 줄에는 각각 두 정수 $L$과 $R$로 이루어진 질의가 주어진다($1 \leq L < R \leq n$).

각 질의마다 질의의 답을 나타내는 정수 하나를 한 줄에 출력한다.