Description

注：easy版本和hard版本本质是不同的问题，无法直接用hard版本的解法通过easy版本。

你已经成功帮助小任解决了老师的审问，小任看到你写的程序，决定把它保存起来，以备后患之忧。

但是他还想要你帮它的功能增强一下，以便对付日后更为复杂的审问。

如果 $x,y$ 为两个字符串，字符串 $y$ 在 $x$ 每一位最大可以匹配的前缀长度的之和称为 $x$ 意义下 $y$ 的价值。

例如 $x="abacd",y="abc"$ 时

在 $x$ 的第一位最多可以匹配 $2$ 位，即：$\textbf{ab}acd$

在 $x$ 的第三位最多可以匹配 $1$ 位，即：$ab \textbf{a} cd$

在其余位置，均只能匹配 $0$ 位。

所以在 $x$ 意义下， $y$ 的价值等于 $1+2=3$。

了解了这些之后，小任会给你一个长度为 $n$ 的字符串 $s$，一个长度为 $m$ 的字符串 $t$，和 $q$ 次询问。

每次询问小任会要求你计算出字符串 $t$ 的一个从下标 $l$ 开始到下标 $r$ 结束的连续子串（字符串 $t$ 的下标从 $1$ 开始），在 $s$ 意义下价值。

小任决定把能够解决这种问题的机器叫做 "RYC自动机"。

Format

Input

第一行给出三个正整数 $n,m,q$，其中 $1\leq n,m,q \leq 3\times 10^5$，分别表示字符串 $s$ 的长度，字符串 $t$ 的长度和老师询问的次数。

第二行给出一个长度为 $n$ 的均由小写字母组成的字符串 $s$，表示小任整理出来的字符串。

第三行给出一个长度为 $m$ 的均由小写字母组成的字符串 $t$, 表示老师整理出来的字符串。

接下来 $q$ 行每行包含两个整数 $l,r$，其中 $1\leq l \leq r \leq m$，表示老师询问的子串在字符串 $t$ 中的下标范围。

Output

一共输出 $q$ 行，每行输出一个整数，表示询问子串在字符串 $s$ 意义下的价值。

Samples

5 5 3
abssa
dasab
1 1
2 3
3 4

0
2
3

Limitation

4s, 1024KiB for each test case.