| Codeforces Round 383 (Div. 1) |
|---|
| Закончено |
Все знают, что девушки в стране Arpa... ладно, мысль вам понятна :D
Все знают, что Arpa — ненормальный человек, он... хорошо, я не могу это объяснить. Mehrdad заинтересовался в причине этого и попросил помощи у Sipa, одного из лучших биологов в стране Arpa. У Sipa есть редактор ДНК.
Sipa провел анализ ДНК Arpa. Редактор ДНК представляет ДНК Arpa как строку S, состоящую из n строчных букв латинского алфавита. Также, у Sipa есть ДНК нормального человека — строка T, состоящая из строчных букв латинского алфавита.
Существует (n + 1) способ изменить ДНК Arpa, способы пронумерованы от 0 до n. i-й из них состоит в том, чтобы вставить строку T между i-м и (i + 1)-м символами строки S (0 ≤ i ≤ n). Если i = 0, то T будет вставлена перед S, а если i = n, то после S.
Mehrdad хочет выбрать наиболее интересный вариант для ДНК Arpa среди этих n + 1 способов. Sipa считает, что ДНК A интереснее ДНК B, если строка A лексикографически меньше строки B. Mehrdad задал Sipa q вопросов:
Пусть даны целые числа l, r, k, x, y. Какой способ наиболее интересный, если рассматривать только такие способы i, что l ≤ i ≤ r и 
? Если существуют несколько наиболее интересных способов, Mehrdad хочет узнать способ с наименьшим номером i.
Так как Sipa — биолог, а не программист, вы должны помочь ему.
Первая строка содержит строки S, T и целое число q (1 ≤ |S|, |T|, q ≤ 105) — ДНК Arpa, ДНК нормального человека и количество вопросов. Строки S и T состоят из строчных букв латинского алфавита.
Следующие q строк содержат описания вопросов Mehrdad. Каждая из этих строк содержит пять целых чисел l, r, k, x, y (0 ≤ l ≤ r ≤ n, 1 ≤ k ≤ n, 0 ≤ x ≤ y < k).
Выведите q целых чисел. j-е из них должно равняться номеру i наиболее интересного способа среди подходящих под условия j-го вопроса. Если нет ни одного способа i, подходящего под условия некоторого вопроса, выведите -1.
abc d 4
0 3 2 0 0
0 3 1 0 0
1 2 1 0 0
0 1 3 2 2
2 3 2 -1
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
1 4 2 -1 2 4 10 1 1 5
Рассмотрим первый тест из примера:
В первом вопросе у Sipa есть два способа: dabc (i = 0) и abdc (i = 2). Последняя (abcd) лучше чем abdc, поэтому ответ равен 2.
В последнем вопросе нет ни одного i удовлетворяющего 0 ≤ i ≤ 1 and 
.
