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

All of us know that girls in Arpa’s land are... ok, you’ve got the idea :D

Anyone knows that Arpa isn't a normal man, he is ... well, sorry, I can't explain it more. Mehrdad is interested about the reason, so he asked Sipa, one of the best biology scientists in Arpa's land, for help. Sipa has a DNA editor.

Sipa put Arpa under the DNA editor. DNA editor showed Arpa's DNA as a string S consisting of n lowercase English letters. Also Sipa has another DNA T consisting of lowercase English letters that belongs to a normal man.

Now there are (n + 1) options to change Arpa's DNA, numbered from 0 to n. i-th of them is to put T between i-th and (i + 1)-th characters of S (0 ≤ i ≤ n). If i = 0, T will be put before S, and if i = n, it will be put after S.

Mehrdad wants to choose the most interesting option for Arpa's DNA among these n + 1 options. DNA A is more interesting than B if A is lexicographically smaller than B. Mehrdad asked Sipa q questions:

Given integers l, r, k, x, y, what is the most interesting option if we only consider such options i that l ≤ i ≤ r and ? If there are several most interesting options, Mehrdad wants to know one with the smallest number i.

Since Sipa is a biology scientist but not a programmer, you should help him.

我们都知道，Arpa 国度里的女孩们……好吧，你已经明白意思了 :D

所有人都知道 Arpa 并非普通人，他其实是……嗯，抱歉，我无法再进一步解释了。Mehrdad 对其中的缘由非常感兴趣，于是向 Arpa 国度最顶尖的生物学家之一 Sipa 寻求帮助。Sipa 拥有一台 DNA 编辑器。

Sipa 将 Arpa 置于 DNA 编辑器下。编辑器将 Arpa 的 DNA 显示为一个长度为 $ n $ 的字符串 $ S $，由小写英文字母组成。此外，Sipa 还拥有另一段属于普通人的 DNA 序列 $ T $，同样由小写英文字母组成。

现在共有 $ n+1 $ 种修改 Arpa 的 DNA 的方案，编号从 $ 0 $ 到 $ n $。其中第 $ i $ 种方案是将 $ T $ 插入到 $ S $ 的第 $ i $ 个字符与第 $ i+1 $ 个字符之间（$ 0 \le i \le n $）。若 $ i = 0 $，则将 $ T $ 插入到 $ S $ 之前；若 $ i = n $，则将 $ T $ 插入到 $ S $ 之后。

Mehrdad 希望在这 $ n+1 $ 种方案中，为 Arpa 的 DNA 选出最有趣的一种。DNA 字符串 $ A $ 比 $ B $ 更有趣，当且仅当 $ A $ 在字典序上小于 $ B $。Mehrdad 向 Sipa 提出了 $ q $ 个询问：

给定整数 $ l, r, k, x, y $，在所有满足 $ l \le i \le r $ 且 的方案 $ i $ 中，最有趣的方案是哪一个？如果存在多个最有趣的方案，Mehrdad 希望得到编号 $ i $ 最小的那个。

由于 Sipa 是一位生物学家而非程序员，你需要帮助他解决这个问题。

The first line contains strings S, T and integer q (1 ≤ |S|, |T|, q ≤ 105) — Arpa's DNA, the DNA of a normal man, and the number of Mehrdad's questions. The strings S and T consist only of small English letters.

Next q lines describe the Mehrdad's questions. Each of these lines contain five integers l, r, k, x, y (0 ≤ l ≤ r ≤ n, 1 ≤ k ≤ n, 0 ≤ x ≤ y < k).

第一行包含字符串 $S$、$T$ 和整数 $q$（$1 ≤ |S|, |T|, q ≤ 10^5$）——分别表示 Arpa 的 DNA 序列、一个正常人的 DNA 序列，以及 Mehrdad 提出的问题数量。字符串 $S$ 和 $T$ 仅由小写英文字母组成。

接下来的 $q$ 行描述 Mehrdad 的问题。每行包含五个整数 $l$、$r$、$k$、$x$、$y$（$0 ≤ l ≤ r ≤ n$, $1 ≤ k ≤ n$, $0 ≤ x ≤ y < k$）。

Print q integers. The j-th of them should be the number i of the most interesting option among those that satisfy the conditions of the j-th question. If there is no option i satisfying the conditions in some question, print -1.

输出 q 个整数。其中第 j 个整数应为满足第 j 个问题条件的最有趣选项的编号 i。若某个问题不存在满足条件的选项 i，则输出 -1。

Explanation of first sample case:

In the first question Sipa has two options: dabc (i = 0) and abdc (i = 2). The latter (abcd) is better than abdc, so answer is 2.

In the last question there is no i such that 0 ≤ i ≤ 1 and .

第一个样例的解释：

在第一个问题中，Sipa 有两种选择：dabc（此时 $i = 0$）和 abdc（此时 $i = 2$）。后者（abcd）优于 abdc，因此答案为 2。

在最后一个问题中，不存在满足 $0 \leq i \leq 1$ 且 的 $i$。