CF741E Arpa’s abnormal DNA and Mehrdad’s deep interest

众所周知，Arpa 的土地上的女孩们都很……好了，你明白我的意思了吧 :D 大家都知道 Arpa 不是一个普通人，他……呃，抱歉，我实在没法再多解释了。Mehrdad 对于原因很感兴趣，于是他向 Arpa 土地上最优秀的生物学家之一 Sipa 寻求帮助。Sipa 拥有一个 DNA 编辑器。 Sipa 将 Arpa 放在 DNA 编辑器下。DNA 编辑器将 Arpa 的 DNA 显示为一个由 $n$ 个小写英文字母组成的字符串 $S$。此外，Sipa 还有属于普通人的 DNA 字符串 $T$，它也仅由小写英文字母组成。 现在有 $(n+1)$ 种更改 Arpa DNA 的方式，编号从 $0$ 到 $n$。第 $i$ 种方式是将 $T$ 插入到 $S$ 的第 $i$ 个和第 $(i+1)$ 个字符之间（$0\leq i\leq n$）。如果 $i=0$，则把 $T$ 插入到 $S$ 之前；如果 $i=n$，则插入到 $S$ 之后。 Mehrdad 想从这 $n+1$ 种方式中为 Arpa 的 DNA 选出最有“趣”的方式。DNA $A$ 比 $B$ 更有趣，当且仅当 $A$ 的字典序小于 $B$。Mehrdad 向 Sipa 提出了 $q$ 个问题： 已知整数 $l,r,k,x,y$，若只考虑满足 $l\leq i\leq r$ 且 $i\mod k$ 落在 $[x,y]$ 范围内的 $i$，哪种插入方式生成的 DNA 字符串在字典序上最小？若有多个最小字典序，输出编号最小的 $i$。 由于 Sipa 是生物学家而不是程序员，你需要帮他解决这个问题。

第一行包含字符串 $S$、$T$ 和整数 $q$（$1\leq|S|,|T|,q\leq 10^5$）——分别为 Arpa 的 DNA、普通人的 DNA 以及 Mehrdad 的问题数。字符串 $S$ 和 $T$ 均只包含小写英文字母。 接下来的 $q$ 行，每行描述一个 Mehrdad 的问题。每行包含五个整数 $l,r,k,x,y$（$0\leq l\leq r\leq n$，$1\leq k\leq n$，$0\leq x\leq y

输出 $q$ 行，每行一个整数，其中第 $j$ 行为第 $j$ 个问题的答案，即在所有满足条件的 $i$ 中，使插入后所得 DNA 字符串字典序最小的 $i$。若不存在满足条件的 $i$，输出 $-1$。

第一个样例的说明： 在第一个询问中，Sipa 有两个选择：dabc（$i=0$）和 abdc（$i=2$）。后者（abcd）的字典序更小，所以答案是 $2$。 在最后一个询问中，没有 $i$ 满足 $0\leq i\leq 1$ 且 $i\mod k$ 落在 $[2,2]$，所以输出 $-1$。 由 ChatGPT 5 翻译