Hongjun Likes Strings

Time limit2sMemory limit512 MB

Summary

For each of up to 100000 queries, find the shortest substring of a fixed string S that contains both given short patterns A and B, allowing overlap.

Level: Hard8 of 10
Topics: String, String matching, Prefix sum, Binary search
Solved: No attempts yet

Problem

Hongjun likes strings, so he keeps making up problems about them.

Here is one of them. Given a string $S$ and two strings $A$ and $B$ , find the shortest contiguous substring of $S$ that contains both $A$ and $B$ as substrings. The occurrence of $A$ and the occurrence of $B$ are allowed to overlap.

Hongjun is smart, so he solved that at once. Then he thought of a harder version, in which the two strings $A$ and $B$ arrive as $Q$ separate questions. He could not find a fast way to answer them, so he decided that short $A$ and $B$ would let him solve it quickly.

Help Hongjun and write a program that answers every question.

Input

The first line contains a string $S$ of length at most $50\,000$ .

The second line contains the number of questions $Q$ , an integer with $0 \le Q \le 100\,000$ .

Each of the next $Q$ lines contains two strings $A$ and $B$ separated by a space. The length of $A$ and the length of $B$ are between $1$ and $4$ .

$S$ , $A$ , and $B$ consist of lowercase English letters only.

Output

Print the answers to the $Q$ questions, one per line. On each line print the minimum length of a contiguous substring of $S$ that contains both $A$ and $B$ as substrings. If no such contiguous substring exists, print $-1$ .

Examples2

Example 1

Input

xudyhduxyz
3
xyz xyz
dyh xyz
dzy xyz

Expected output

3
8
-1

Example 2
Input
```
aaaa
4
a a
aa aaa
aaaa a
b a
```
Expected output
```
1
3
4
-1
```