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.

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* ≤ 10^{5}$) — 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.

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 .