홍준이는 문자열을 좋아해

시간 제한2초메모리 제한512 MB

요약

길이 50000 이하의 문자열 S와 최대 100000개의 질의가 주어질 때, 각 질의의 두 짧은 패턴 A와 B를 모두 부분 문자열로 포함하는 가장 짧은 연속 부분 문자열의 길이를 구한다.

난이도: 어려움10점 중 8점
유형: 문자열, 문자열 매칭, 누적 합, 이분 탐색
정답자: 아직 제출이 없습니다

문제

홍준이는 문자열을 좋아해서 문자열과 관련된 문제를 여러 개 만들어 보고 있습니다.

그중 하나는 이렇습니다. 문자열 $S$ 와 두 문자열 $A$ , $B$ 가 주어질 때, $A$ 와 $B$ 를 모두 부분 문자열로 포함하는 $S$ 의 연속 부분 문자열 가운데 길이가 가장 짧은 것을 구합니다. $A$ 가 나타나는 자리와 $B$ 가 나타나는 자리는 겹쳐도 됩니다.

홍준이는 똑똑해서 이 문제를 금방 풀어버렸습니다. 그래서 두 문자열 $A$ 와 $B$ 가 질문으로 $Q$ 번 들어오는, 한층 더 어려운 문제를 생각했습니다. 답을 빠르게 구하는 방법을 고민하던 홍준이는 너무 어려워서 $A$ 와 $B$ 의 길이가 짧다면 빨리 풀 수 있을 것으로 생각하고 있습니다.

홍준이를 도와 질문마다 답을 구하는 프로그램을 작성하세요.

입력

첫째 줄에 길이가 $50\,000$ 이하인 문자열 $S$ 가 주어집니다.

둘째 줄에 질문의 개수 $Q$ 가 주어집니다. $Q$ 는 $0 \le Q \le 100\,000$ 인 정수입니다.

셋째 줄부터 $Q$ 개의 줄에 걸쳐 두 문자열 $A$ 와 $B$ 가 공백으로 구분되어 주어집니다. $A$ 와 $B$ 의 길이는 각각 $1$ 이상 $4$ 이하입니다.

$S$ , $A$ , $B$ 는 모두 영문 알파벳 소문자로만 이루어져 있습니다.

출력

$Q$ 개의 줄에 걸쳐 각 질문의 답을 한 줄에 하나씩 출력합니다. 각 줄에는 $A$ 와 $B$ 를 모두 부분 문자열로 포함하는 $S$ 의 연속 부분 문자열의 최소 길이를 출력합니다. 그런 연속 부분 문자열이 존재하지 않으면 $-1$ 을 출력합니다.

예제2

예제 1

입력

xudyhduxyz
3
xyz xyz
dyh xyz
dzy xyz

예상 출력

3
8
-1

예제 2
입력
```
aaaa
4
a a
aa aaa
aaaa a
b a
```
예상 출력
```
1
3
4
-1
```