English · Original
Chinese · Translation
Formal · Original
_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.
<center></center>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.
## Input
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_).
## Output
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_.
[samples]
## Note
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 .
我们知道，Arpa 地区的女生是……好吧，你懂的 :D
任何人都知道 Arpa 不是一个普通人，他是……呃，抱歉，我无法进一步解释。Mehrdad 对此感到好奇，于是向 Arpa 地区最优秀的生物学家之一 Sipa 寻求帮助。Sipa 拥有一个 DNA 编辑器。
Sipa 将 Arpa 放入 DNA 编辑器中。DNA 编辑器将 Arpa 的 DNA 显示为一个由 #cf_span[n] 个小写英文字母组成的字符串 #cf_span[S]。同时，Sipa 还拥有另一个属于正常人的 DNA #cf_span[T]，它也由小写英文字母组成。
现在有 #cf_span[(n + 1)] 种修改 Arpa 的 DNA 的方案，编号从 #cf_span[0] 到 #cf_span[n]。第 #cf_span[i] 种方案是将 #cf_span[T] 插入到 #cf_span[S] 的第 #cf_span[i] 个字符与第 #cf_span[(i + 1)] 个字符之间（#cf_span[0 ≤ i ≤ n]）。如果 #cf_span[i = 0]，则 #cf_span[T] 将被插入到 #cf_span[S] 之前；如果 #cf_span[i = n]，则 #cf_span[T] 将被插入到 #cf_span[S] 之后。
Mehrdad 希望在这些 #cf_span[n + 1] 种方案中选择最“有趣”的一个。如果 DNA #cf_span[A] 在字典序上小于 #cf_span[B]，则称 #cf_span[A] 比 #cf_span[B] 更“有趣”。Mehrdad 向 Sipa 提出了 #cf_span[q] 个问题：
给定整数 #cf_span[l, r, k, x, y]，如果我们只考虑满足 #cf_span[l ≤ i ≤ r] 且 #cf_span[i \bmod k \in [x, y]] 的选项 #cf_span[i]，那么最“有趣”的选项是哪一个？如果有多个最“有趣”的选项，Mehrdad 希望知道编号最小的那个 #cf_span[i]。
由于 Sipa 是生物学家而非程序员，你需要帮助他。
第一行包含字符串 #cf_span[S]、#cf_span[T] 和整数 #cf_span[q]（#cf_span[1 ≤ |S|, |T|, q ≤ 10^5]）—— Arpa 的 DNA、正常人的 DNA 以及 Mehrdad 的问题数量。字符串 #cf_span[S] 和 #cf_span[T] 仅由小写英文字母组成。
接下来的 #cf_span[q] 行描述了 Mehrdad 的问题。每行包含五个整数 #cf_span[l, r, k, x, y]（#cf_span[0 ≤ l ≤ r ≤ n], #cf_span[1 ≤ k ≤ n], #cf_span[0 ≤ x ≤ y < k]）。
请输出 #cf_span[q] 个整数。第 #cf_span[j] 个整数应为满足第 #cf_span[j] 个问题条件的最“有趣”选项的编号 #cf_span[i]。如果某个问题中没有满足条件的选项 #cf_span[i]，请输出 _-1_。
第一个样例的解释：
在第一个问题中，Sipa 有两个选项：_dabc_（#cf_span[i = 0]）和 _abdc_（#cf_span[i = 2]）。后者（_abcd_）优于 _abdc_，因此答案是 #cf_span[2]。
在最后一个问题中，不存在满足 #cf_span[0 ≤ i ≤ 1] 且 #cf_span[i \bmod 3 \in [2, 2]] 的 #cf_span[i]。
## Input
第一行包含字符串 #cf_span[S]、#cf_span[T] 和整数 #cf_span[q]（#cf_span[1 ≤ |S|, |T|, q ≤ 10^5]）—— Arpa 的 DNA、正常人的 DNA 以及 Mehrdad 的问题数量。字符串 #cf_span[S] 和 #cf_span[T] 仅由小写英文字母组成。接下来的 #cf_span[q] 行描述了 Mehrdad 的问题。每行包含五个整数 #cf_span[l, r, k, x, y]（#cf_span[0 ≤ l ≤ r ≤ n], #cf_span[1 ≤ k ≤ n], #cf_span[0 ≤ x ≤ y < k]）。
## Output
请输出 #cf_span[q] 个整数。第 #cf_span[j] 个整数应为满足第 #cf_span[j] 个问题条件的最“有趣”选项的编号 #cf_span[i]。如果某个问题中没有满足条件的选项 #cf_span[i]，请输出 _-1_。
[samples]
## Note
第一个样例的解释：
在第一个问题中，Sipa 有两个选项：_dabc_（#cf_span[i = 0]）和 _abdc_（#cf_span[i = 2]）。后者（_abcd_）优于 _abdc_，因此答案是 #cf_span[2]。
在最后一个问题中，不存在满足 #cf_span[0 ≤ i ≤ 1] 且 #cf_span[i \bmod 3 \in [2, 2]] 的 #cf_span[i]。
**Definitions**
Let $ S \in \Sigma^* $ be Arpa’s DNA string of length $ n $, and $ T \in \Sigma^* $ be the normal man’s DNA string.
For each $ i \in \{0, 1, \dots, n\} $, define the modified DNA string:
$$
A_i = S[0:i] + T + S[i:n]
$$
where $ S[0:i] $ is the prefix of $ S $ of length $ i $, and $ S[i:n] $ is the suffix starting at index $ i $.
**Constraints**
1. $ 1 \leq |S|, |T|, q \leq 10^5 $
2. For each query:
- $ 0 \leq l \leq r \leq n $
- $ 1 \leq k \leq n $
- $ 0 \leq x \leq y < k $
**Objective**
For each query $ (l, r, k, x, y) $, find the smallest index $ i \in [l, r] $ such that:
$$
A_i \text{ is lexicographically minimal among all } A_j \text{ for } j \in [l, r] \text{ and } j \bmod k \in [x, y]
$$
If no such $ i $ exists, output $ -1 $.
API Response (JSON)
{
"problem": {
"name": "E. Arpa’s abnormal DNA and Mehrdad’s deep interest",
"description": {
"content": "_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",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF741E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "_All of us know that girls in Arpa’s land are... ok, you’ve got the idea :D_\n\nAnyone knows that Arpa isn't a normal man, he is ... well, sorry, I can't explain it more. Mehrdad is interested about the...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "我们知道，Arpa 地区的女生是……好吧，你懂的 :D\n\n任何人都知道 Arpa 不是一个普通人，他是……呃，抱歉，我无法进一步解释。Mehrdad 对此感到好奇，于是向 Arpa 地区最优秀的生物学家之一 Sipa 寻求帮助。Sipa 拥有一个 DNA 编辑器。\n\nSipa 将 Arpa 放入 DNA 编辑器中。DNA 编辑器将 Arpa 的 DNA 显示为一个由 #cf_span[n] 个小写...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ S \\in \\Sigma^* $ be Arpa’s DNA string of length $ n $, and $ T \\in \\Sigma^* $ be the normal man’s DNA string. \nFor each $ i \\in \\{0, 1, \\dots, n\\} $, define the modified DNA s...",
"is_translate": false,
"language": "Formal"
}
]
}