在在线聊天时，我们可以保存某人说的话来形成他的“经典语录”。小 Q 也喜欢这样做。不仅如此，他甚至可以修改原始的文字。形式化地，假设某人说了一个长度为 $n$ 的字符串 $S$。小 Q 会选择 $S$ 的一个连续子串（可以为空）并将其删除，然后将剩余的两部分拼接起来，得到一个新的字符串 $S'$。例如，他可以从字符串 “I am not SB” 中删除 “not ”，使得新的字符串 $S'$ 变为 “I am SB”。

在做了很多次这样的操作后，小 Q 发现字符串 $T$ 经常作为 $S'$ 的连续子串出现。

现在给定字符串 $S$ 和 $T$，小 Q 有 $k$ 次询问。每次询问的格式如下：给定 $L$ 和 $R$，小 Q 将删除一个子串，使得剩余的两部分为 $S[1..i]$ 和 $S[j..n]$，其中整数对 $(i, j)$ 是在所有满足 $1 \le i \le L$ 且 $R \le j \le n$ 的对中等概率选取的。你的目标是求出 $T$ 在结果字符串中出现次数的期望值 $E$，并输出 $E \cdot L \cdot (n - R + 1)$ 的值。

$T$ 的所有出现位置都必须计入，即使它们重叠。各次询问是独立的：字符串 $S$ 实际上并没有转化为 $S'$，且对于所有询问，$S$ 保持不变。

输入格式

第一行包含三个整数 $n, m$ 和 $k$，分别表示 $S$ 的长度、 $T$ 的长度以及询问次数（$1 \le n \le 5 \cdot 10^4, 1 \le m \le 100, 1 \le k \le 5 \cdot 10^4$）。

第二行包含一个由 $n$ 个小写英文字母组成的字符串 $S$。下一行包含一个由 $m$ 个小写英文字母组成的字符串 $T$。接下来的 $k$ 行，每行包含一个询问，由两个整数 $L$ 和 $R$ 组成（$1 \le L < R \le n$）。

输出格式

对于每次询问，输出一行，包含一个整数，即该询问的答案。

样例

输入 1

8 5 4
iamnotsb
iamsb
4 7
3 7
3 8
2 7

输出 1

1
1
0
0