All of us know that girls in Arpa’s land are... ok, you’ve got the idea :DAnyone 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 \le i \le 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 \le i \le 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 \le |S|,|T|,q \le 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 \le l \le r \le n, 1 \le k \le n, 0 \le x \le y \lt 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.

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 \le i \le 1 and .