String
Description
Given two strings $S_1$ and $S_2$ of equal length (indexed from $1$).
Now you need to answer $q$ queries, with each query consists of a string $T$.
The query asks how many triplets of integers $(i, j, k)\ (1\le i \le j < k\le |S_1|)$ satisfy the condition $S_1[i,j]+S_2[j+1,k]=T$.
Here $S[l,r]$ denotes the substring of $S$ with index form $l$ to $r$, and "+" denotes concatenation of strings.
The first line contains a string $S_1$ .
The second line contains a string $S_2$ .
It is guaranteed that $1\le|S_1|=|S_2|\le 10^5$.
The third line contains a positive integer $q\ (1\leq q\leq 2\times 10^5)$, representing the number of queries.
The next $q$ lines each contain a string $T\ (1\leq |T|\leq 2\times 10^5)$, representing the query strings.
It is guaranteed that $\sum|T|\leq 2\times 10^5$ and all the strings input only consisting of lowercase letters.
For each query, output a line with a positive integer representing the number of triplets that satisfy the condition.
Input
The first line contains a string $S_1$ .
The second line contains a string $S_2$ .
It is guaranteed that $1\le|S_1|=|S_2|\le 10^5$.
The third line contains a positive integer $q\ (1\leq q\leq 2\times 10^5)$, representing the number of queries.
The next $q$ lines each contain a string $T\ (1\leq |T|\leq 2\times 10^5)$, representing the query strings.
It is guaranteed that $\sum|T|\leq 2\times 10^5$ and all the strings input only consisting of lowercase letters.
Output
For each query, output a line with a positive integer representing the number of triplets that satisfy the condition.
aaababaa
aababbca
7
aa
abb
aab
ab
abc
bb
ba
3
1
3
2
2
1
0