我们都知道 Arpa 土地上的女孩......好吧,你已经明白了 :D
任何人都知道Arpa不是一个正常人,他是……好吧,抱歉,我无法解释更多。迈赫达德对其中的原因很感兴趣,因此他向阿尔帕土地上最优秀的生物科学家之一西帕寻求帮助。 Sipa 有一个 DNA 编辑器。
Sipa 将 Arpa 置于 DNA 编辑器之下。 DNA编辑器将Arpa的DNA显示为由n个小写英文字母组成的字符串S。西帕还有另一个由小写英文字母组成的DNA T,属于正常人。
现在有 (n + 1) 个选项可以改变 Arpa 的 DNA,编号从 0 到 n。其中第 i 个是将 T 放在 S 的第 i 个和第 (i + 1) 个字符之间(0 ≤ i ≤ n)。如果 i = 0,则 T 将放在 S 之前,如果 i = n,则将放在 S 之后。
Mehrdad 想要在这 n + 1 个选项中选择对 Arpa 的 DNA 最感兴趣的选项。如果 DNA A 在字典顺序上小于 B,则 DNA A 比 B 更有趣。Mehrdad 向 Sipa 问了 q 问题:
给定整数 l、r、k、x、y,如果我们只考虑 l ≤ i ≤ r 和 $$x \leq (i \bmod k) \leq y$$ 的选项 i,最有趣的选项是什么?如果有几个最有趣的选项,Mehrdad 想要知道数字 i 最小的一个。
由于Sipa是一名生物学科学家而不是程序员,所以你应该帮助他。
输入
第一行包含字符串 S、T 和整数 q (1 ≤ |S|, |T|, q ≤ 105) — Arpa 的 DNA、正常人的 DNA 以及 Mehrdad 的问题数。字符串 S 和 T 仅由小英文字母组成。
接下来的 q 行描述了 Mehrdad 的问题。每行包含五个整数 l、r、k、x、y(0 ≤ l ≤ r ≤ n、1 ≤ k ≤ n、0 ≤ x ≤ y < k)。
输出
打印 q 个整数。其中第j个应该是满足第j题条件的选项中最感兴趣的第i个选项。如果某个问题中没有满足条件的选项,则打印-1。
示例
输入 #1
abc d 4 0 3 2 0 0 0 3 1 0 0 1 2 1 0 0 0 1 3 2 2
输出 #1
2 3 2 -1
输入 #2
abbbbbbaaa baababaaab 10 1 2 1 0 0 2 7 8 4 7 2 3 9 2 8 3 4 6 1 1 0 8 5 2 4 2 8 10 4 7 7 10 1 0 0 1 4 6 0 2 0 9 8 0 6 4 8 5 0 1
输出 #2
1 4 2 -1 2 4 10 1 1 5
注意
第一个示例案例的说明:
在第一个问题中,Sipa 有两个选项:dabc (i = 0) 和 abdc (i = 2)。后者 (abcd) 比 abdc 好,所以答案是 2。
在最后一个问题中,没有 i 使得 0 ≤ i ≤ 1 且 $$2 \leq ( i \bmod 3 ) \leq 2$$。