{"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 reason, so he asked Sipa, one of the best biology scientists in Arpa's land, for help. Sipa has a DNA editor.\n\n<center>![image](https://espresso.codeforces.com/c9f871ceb6cf44beaf842d9538a30ec8cea3e8c4.png)</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.\n\nNow 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_.\n\nMehrdad 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:\n\nGiven 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_.\n\nSince Sipa is a biology scientist but not a programmer, you should help him.\n\n## Input\n\nThe 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.\n\nNext _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_).\n\n## Output\n\nPrint _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_.\n\n[samples]\n\n## Note\n\nExplanation of first sample case:\n\nIn 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.\n\nIn the last question there is no _i_ such that 0 ≤ _i_ ≤ 1 and .","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] 个小写英文字母组成的字符串 #cf_span[S]。同时，Sipa 还拥有另一个属于正常人的 DNA #cf_span[T]，它也由小写英文字母组成。\n\n现在有 #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] 之后。\n\nMehrdad 希望在这些 #cf_span[n + 1] 种方案中选择最“有趣”的一个。如果 DNA #cf_span[A] 在字典序上小于 #cf_span[B]，则称 #cf_span[A] 比 #cf_span[B] 更“有趣”。Mehrdad 向 Sipa 提出了 #cf_span[q] 个问题：\n\n给定整数 #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]。\n\n由于 Sipa 是生物学家而非程序员，你需要帮助他。\n\n第一行包含字符串 #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] 仅由小写英文字母组成。\n\n接下来的 #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]）。\n\n请输出 #cf_span[q] 个整数。第 #cf_span[j] 个整数应为满足第 #cf_span[j] 个问题条件的最“有趣”选项的编号 #cf_span[i]。如果某个问题中没有满足条件的选项 #cf_span[i]，请输出 _-1_。\n\n第一个样例的解释：\n\n在第一个问题中，Sipa 有两个选项：_dabc_（#cf_span[i = 0]）和 _abdc_（#cf_span[i = 2]）。后者（_abcd_）优于 _abdc_，因此答案是 #cf_span[2]。\n\n在最后一个问题中，不存在满足 #cf_span[0 ≤ i ≤ 1] 且 #cf_span[i \\bmod 3 \\in [2, 2]] 的 #cf_span[i]。\n\n## Input\n\n第一行包含字符串 #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]）。\n\n## Output\n\n请输出 #cf_span[q] 个整数。第 #cf_span[j] 个整数应为满足第 #cf_span[j] 个问题条件的最“有趣”选项的编号 #cf_span[i]。如果某个问题中没有满足条件的选项 #cf_span[i]，请输出 _-1_。\n\n[samples]\n\n## Note\n\n第一个样例的解释：\n\n在第一个问题中，Sipa 有两个选项：_dabc_（#cf_span[i = 0]）和 _abdc_（#cf_span[i = 2]）。后者（_abcd_）优于 _abdc_，因此答案是 #cf_span[2]。\n\n在最后一个问题中，不存在满足 #cf_span[0 ≤ i ≤ 1] 且 #cf_span[i \\bmod 3 \\in [2, 2]] 的 #cf_span[i]。","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 string:  \n$$\nA_i = S[0:i] + T + S[i:n]\n$$  \nwhere $ S[0:i] $ is the prefix of $ S $ of length $ i $, and $ S[i:n] $ is the suffix starting at index $ i $.\n\n**Constraints**  \n1. $ 1 \\leq |S|, |T|, q \\leq 10^5 $  \n2. For each query:  \n   - $ 0 \\leq l \\leq r \\leq n $  \n   - $ 1 \\leq k \\leq n $  \n   - $ 0 \\leq x \\leq y < k $\n\n**Objective**  \nFor each query $ (l, r, k, x, y) $, find the smallest index $ i \\in [l, r] $ such that:  \n$$\nA_i \\text{ is lexicographically minimal among all } A_j \\text{ for } j \\in [l, r] \\text{ and } j \\bmod k \\in [x, y]\n$$  \nIf no such $ i $ exists, output $ -1 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF741E","tags":["data structures","string suffix structures"],"sample_group":[["abc d 4\n0 3 2 0 0\n0 3 1 0 0\n1 2 1 0 0\n0 1 3 2 2","2 3 2 -1"],["abbbbbbaaa baababaaab 10\n1 2 1 0 0\n2 7 8 4 7\n2 3 9 2 8\n3 4 6 1 1\n0 8 5 2 4\n2 8 10 4 7\n7 10 1 0 0\n1 4 6 0 2\n0 9 8 0 6\n4 8 5 0 1","1 4 2 -1 2 4 10 1 1 5"]],"created_at":"2026-03-03 11:00:39"}}