듣기 평가 연습

알고리즘의 중요성이 널리 알려지면서 SUAPC에 참가하려는 사람도 늘었다. 이런 흐름에 맞춰 SUAPC에 듣기 평가 영역이 새로 생겼다. 래오는 코딩은 할 줄 알지만 듣기는 약해서, 기출 문제로 듣기 평가를 연습하려 한다.

래오의 단어장은 길이 $N$의 문자열 $S$로, 기출 문제집은 길이 $M$의 문자열 $T$로 주어진다. 래오는 다음과 같은 형식의 연습 문제를 $Q$번 풀어야 한다. 두 문자열의 정확히 앞 $k$글자가 서로 같을 때, 두 문자열을 $k$-유사한 관계라 하자. 두 문자열 중 하나의 길이가 $k$ 미만이거나, 두 문자열의 앞 $k+1$글자 이상이 서로 같으면 두 문자열은 $k$-유사하지 않다.

• $i$ $j$ $k$ : $T$의 부분 문자열 $T_i T_{i+1} ... T_j$와 $k$-유사한 $S$의 부분 문자열의 개수를 출력한다.

부분 문자열이란 문자열의 연속된 일부를 말한다. 부분 문자열은 빈 문자열일 수 없다.

첫째 줄에 단어장의 길이 $N$, 기출 문제집의 길이 $M$, 연습 문제의 개수 $Q$가 공백으로 구분되어 주어진다. ($1 \leq N, M, Q \leq 100\,000$)

둘째 줄에 알파벳 소문자로 이루어진 길이 $N$의 문자열 $S$가 주어진다.

셋째 줄에 알파벳 소문자로 이루어진 길이 $M$의 문자열 $T$가 주어진다.

이후 $Q$개의 줄에 걸쳐 연습 문제가 i j k와 같은 형태로 주어진다. ($1 \leq i \leq j \leq M$, $0 \leq k \leq M$)

각 연습 문제에 대한 답을 한 줄에 하나씩 순서대로 출력한다.