题目描述

熟练的程序设计竞赛选手都很熟悉经典的“统计模式串在文本串中出现次数”的问题。通常它是这样表述的：给定模式串 $s$ 和文本串 $t$，要求找出有多少个位置可以作为起点，使得字符串 $s$ 出现在字符串 $t$ 中。

不幸的是，这个问题已经有很多算法可以解决，因此它本身只能作为练习题，而不太像一道奥林匹克题目。不过，和许多标准问题一样，它很容易被加强：现在我们关心的不是整个字符串 $s$ 和 $t$，而是它们的某些子串：

$$s[l_1\ldots r_1],\quad t[l_2\ldots r_2].$$

给定 $q$ 个询问，第 $i$ 个询问给出两个子串：

$$\bar{s}=s[l_{1i}\ldots r_{1i}],\quad \bar{t}=t[l_{2i}\ldots r_{2i}].$$

你需要对于每个询问，计算字符串 $\bar{s}$ 在字符串 $\bar{t}$ 中出现的次数。

输入格式

第一行包含字符串 $s$。

第二行包含字符串 $t$。

第三行包含一个整数 $q$，表示询问数量。

接下来 $q$ 行，每行包含四个整数 $l_1,r_1,l_2,r_2$，描述一个询问。

满足：

$$1 \le |s|,|t| \le 2\cdot 10^5,$$

字符串 $s,t$ 均由小写英文字母组成；

$$1 \le q \le 5\cdot 10^5,$$ $$1 \le l_1 \le r_1 \le |s|,\quad 1 \le l_2 \le r_2 \le |t|.$$

输出格式

输出 $q$ 个整数，分别表示每个询问的答案。每个答案占一行。

样例

abb
ababababb
5
1 2 1 7
2 3 2 9
3 3 4 7
1 2 2 4
1 1 1 9

3
1
2
1
4

样例解释

考虑样例中的询问。为了方便说明，出现位置使用字符串 $t$ 中的原始下标。

1. $\bar{s}=\texttt{ab}$，$\bar{t}=\texttt{abababa}$。$\bar{s}$ 在 $\bar{t}$ 中从位置 $1,3,5$ 开始出现。
2. $\bar{s}=\texttt{bb}$，$\bar{t}=\texttt{babababb}$。$\bar{s}$ 在 $\bar{t}$ 中从位置 $8$ 开始出现。
3. $\bar{s}=\texttt{b}$，$\bar{t}=\texttt{baba}$。$\bar{s}$ 在 $\bar{t}$ 中从位置 $4,6$ 开始出现。
4. $\bar{s}=\texttt{ab}$，$\bar{t}=\texttt{bab}$。$\bar{s}$ 在 $\bar{t}$ 中从位置 $3$ 开始出现。
5. $\bar{s}=\texttt{a}$，$\bar{t}=\texttt{ababababb}$。$\bar{s}$ 在 $\bar{t}$ 中从位置 $1,3,5,7$ 开始出现。

子任务

| 组别 | 分数 | $|s|$ | $|t|$ | $q$ | 必须通过的组 | 说明 | | ---- | ---: | ----------------: | ----------------: | ----------------: | ------------ | -------- | | 0 | 0 | — | — | — | — | 样例测试 | | 1 | 7 | $\le 100$ | $\le 100$ | $\le 10^3$ | 0 | | | 2 | 18 | $\le 10^4$ | $\le 10^4$ | $\le 10^4$ | 0,1 | | | 3 | 35 | $\le 10^5$ | $\le 10^5$ | $\le 10^5$ | 0,1,2 | | | 4 | 40 | $\le 2\cdot 10^5$ | $\le 2\cdot 10^5$ | $\le 5\cdot 10^5$ | 0,1,2,3 | 离线测试 |