题目描述

现某戏剧拟从一段优美的文字中截取若干片段作为剧本中的台词。具体的要求如下：

1. 剧本由若干句从给定文字中截取的台词组成。即，每句台词都必须是给定的字符串 $S$ 的一个子串。
2. 相邻的两句台词必须可以相互衔接。具体而言，给定一衔接系数 $k$，每一句台词的长度为 $k$ 的后缀必须和下一句台词的长度为 $k$ 的前缀相同。
3. 剧本最初的台词和最后的台词已经确定，第一句台词为 $S_{l_1\ldots r_1}$，最后一句台词为 $S_{l_2\ldots r_2}$。

现已知字符串 $S$，请你编写程序，对于多组给定的 $l_1, r_1, l_2, r_2$ 和衔接系数 $k$，计算是否存在满足上述限制的剧本。 如果存在，至少包含多少句台词。

输入格式

第一行包含一个由小写英文字母构成的字符串 $S$。

第二行包含一个正整数 $q$。

接下来 $q$ 行，每行包含五个由空格分开的正整数 $l_1, r_1, l_2, r_2, k$，描述一组询问。

输出格式

对于每组询问，输出一行一个整数。如果不存在满足题中限制的剧本，则输出 -1。否则输出所求的最小值。

abaxyaba
4
2 3 7 8 2
1 2 7 8 2
5 8 1 4 3
5 8 1 4 4

1
3
2
-1

提示

【样例 1 解释】

对于第一组询问，给定的第一句台词和最后一句台词是完全相同的，因此剧本可以仅包含这一个字符串。

对于第二组询问，一种可行的方案为 $\{\text{ab}, \text{aba}, \text{ba}\}$。

对于第三组询问，一种可行的方案为 $\{\text{yaba}, \text{abax}\}$。

对于第四组询问，可以证明不存在可以满足题目中要求的剧本。

【样例 2】

见选手目录下的 lines/lines2.in 与 lines/lines2.ans。

样例 $2$ 满足测试点 $2\sim 3$ 的限制。

【样例 3】

见选手目录下的 lines/lines3.in 与 lines/lines3.ans。

样例 $3$ 满足测试点 $2\sim 3$ 的限制。

【样例 4】

见选手目录下的 lines/lines4.in 与 lines/lines4.ans。

样例 $4$ 满足测试点 $11\sim 12$ 的限制。

【样例 5】

见选手目录下的 lines/lines5.in 与 lines/lines5.ans。

样例 $5$ 满足测试点 $11\sim 12$ 的限制。

【子任务】

对于全部的测试数据，保证 $1 \le |S| \le 10^6$，$1 \le q \le 10^6$，$1 \le l_1 + k - 1 \le r_1 \le |S|$，$1 \le l_2 + k - 1 \le r_2 \le |S|$，$1 \le k \le |S|$。