Script Dialogue Chain Construction

In this problem, you are given a string S and several queries. For each query you are given five integers: l₁, r₁, l₂, r₂ and a connection coefficient k. The goal is to determine whether it is possible to construct a script (dialogue) consisting of several lines, each of which is a substring of S, satisfying the following conditions:

1. Every dialogue line is taken as a substring of S. (A substring is a contiguous segment of S.)
2. Any two adjacent lines must be "connectable". Specifically, if the connection coefficient is k, then the last k characters (i.e. the k-length suffix) of the previous line must be identical to the first k characters (i.e. the k-length prefix) of the next line.
3. The first and the last lines of the script are fixed. The first line is the substring S[l₁...r₁] and the last line is S[l₂...r₂].

If it is possible to construct such a script, you must output the minimum number of lines in some valid script; otherwise, output -1.

Note on substrings: Every chosen substring must have length at least k (since we need a k-length prefix and suffix). In particular, if a substring has length exactly k, then its prefix and suffix are identical.

---

Observation:

Any valid dialogue line (substring) can be identified by its first k characters and its last k characters. We say that there is a directed edge from string u to string v if there exists a substring of S whose first k characters are u and whose last k characters are v (with the additional condition that the substring length is at least k). Then, a valid script (ignoring the fixed first and last lines) corresponds to selecting a sequence of such edges such that consecutive edges “connect”: the second component of one edge equals the first component of the next.

Let the fixed first line be A = S[l₁...r₁] and its associated pair be $$ (P_A, Q_A) = (S[l_1 \ldots l_1+k-1],\; S[r_1-k+1 \ldots r_1]). $$ Similarly, let the fixed last line be B = S[l₂...r₂] with $$ (P_B, Q_B) = (S[l_2 \ldots l_2+k-1],\; S[r_2-k+1 \ldots r_2]). $$ If A and B are identical then a valid script simply consists of one line and the answer is 1. Otherwise, let u = Q_A and v = P_B. You need to check whether there exists a path from u to v in the directed graph defined earlier. If the shortest path has d edges, then the minimum number of lines in the script is d + 2 (we count the fixed first and last lines). If no such path exists, output -1.

This problem requires careful construction of the graph. For a given query (with its own k), you need to find all distinct substrings of length k in S and record the positions at which they occur. Then, for two distinct substrings u and v, a directed edge from u to v exists if there is some occurrence of u at position a and some occurrence of v at position b such that the substring starting at a and ending at b + k - 1 is valid (i.e. its length is at least k, with the careful case that if a = b then necessarily u = v).

Your task is to answer each query accordingly.

inputFormat

The first line contains the string S.

The second line contains an integer Q denoting the number of queries.

Each of the following Q lines contains five integers l₁ r₁ l₂ r₂ k separated by spaces.

All indices are 1-indexed. It is guaranteed that the substrings S[l₁...r₁] and S[l₂...r₂] have lengths at least k.

outputFormat

For each query, output a single line containing the minimum number of dialogue lines in a valid script satisfying the restrictions. If no valid construction exists, output -1.

sample

ababa
3
1 3 3 5 1
1 2 4 5 1
1 3 3 5 2

1
2
3

</p>