← 返回题目列表

Codeforces · 741/E

E. Arpa的异常DNA和Mehrdad的浓厚兴趣

中文机器翻译题面 查看原题

我们都知道 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$$。