Listening Test Practice

The importance of algorithms has become widely known, so more people now want to join SUAPC. Following this trend, SUAPC added a listening test section. Rao can code but is weak at listening, so he plans to practice the listening test with past exam problems.

Rao's vocabulary list is a string $S$ of length $N$, and his past exam collection is a string $T$ of length $M$. Rao must solve $Q$ practice problems of the following form. When two strings have the same first $k$ characters, they are said to be $k$-similar. Two strings are not $k$-similar if one of them has length less than $k$, or if they match in their first $k+1$ or more characters.

• $i$ $j$ $k$: Output the number of substrings of $S$ that are $k$-similar to the substring $T_i T_{i+1} ... T_j$ of $T$.

A substring is a contiguous part of a string. A substring cannot be empty.

The first line contains $N$, $M$, and $Q$ separated by spaces, where $N$ is the length of the vocabulary list, $M$ is the length of the exam collection, and $Q$ is the number of practice problems. ($1 \leq N, M, Q \leq 100\,000$)

The second line contains the string $S$ of length $N$, made of lowercase English letters.

The third line contains the string $T$ of length $M$, made of lowercase English letters.

The next $Q$ lines each give a practice problem in the form i j k. ($1 \leq i \leq j \leq M$, $0 \leq k \leq M$)

Print the answer to each practice problem on its own line, in order.