E. Необычный ДНК Arpa и повышенный интерес Mehrdad
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Все знают, что девушки в стране 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 .