L-Striking String Problem_2025牛客国庆集训派对day1

时间限制：C/C++/Rust/Pascal 8秒，其他语言16秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

NIO is given two strings $S$ and $T$ consisting of lowercase letters, an integer $k$ and $2k$ integers $l_i, r_i\ (1\leq i \leq k)$ .

Define $U = S[l_1, r_1] + S[l_2, r_2] + \cdots + S[l_k, r_k]$ . He has $q$ queries, each described by two integers $x$ and $y$ . For a query, he wants to know the number of times that $T$ appears in $U[x, y]$ . Help him!

$S[l, r]$ is $S_lS_{l + 1}\cdots S_r$ .
$S + T$ is $S_1S_2\cdots S_{|S|}T_1T_2\cdots T_{|T|}$ .

输入描述:

The first line contains a single string .

The second line contains a single string .

The third line contains two integers  and .

Each of the next  lines contains two integers  and .

Each of the next  lines contains two integers  and .

输出描述:

Print  lines. The -th of them contains a single integer - the answer to the -th query.

示例1

输入

复制

输出

复制

题目描述

输入描述:

输出描述:

输入

输出

说明