Mango es un gato que vive en la casa de al lado. Su nombre proviene del hecho de que su color es similar al color del jugo de mango. No sé si a Mango le gusta este nombre.

Como la mayoría de los gatos, Mango es lindo. Mango, a quien mucha gente quiere, a veces se convierte en el tema de bromas humorísticas como "El mango se ve delicioso" o "Eso es un gato, no un mango". Recientemente, Mango se ha convertido en el héroe de un meme sobre la generación de las siguientes oraciones recursivas.

Digamos que tenemos la cadena inicial $M_0$ y la cadena de reglas $S$. Para cualquier entero positivo $i$, $M_i$ se define como la cadena en la que cada carácter "$" es reemplazado por la cadena $M_{i-1}$.

Es fácil construir las primeras cadenas de este tipo. Por ejemplo, si decimos que $M_0$ es "That’s a cat, not a mango", y $S$ es "That’s a "$", not a "$"", entonces $M_0$, $M_1$ y $M_2$ se ven de la siguiente manera:

• $M_0$: "That’s a cat, not a mango".
• $M_1$: "That’s a "That’s a cat, not a mango", not a "That’s a cat, not a mango"".
• $M_2$: "That’s a "That’s a "That’s a cat, not a mango", not a "That’s a cat, not a mango"", not a "That’s a "That’s a cat, not a mango", not a "That’s a cat, not a mango""".

No solo $M_3$ y $M_4$, sino también $M_{1000}$ pueden construirse usando el mismo principio. Sin embargo, incluso $M_5$ ya es bastante largo. Aun así, me pregunto, para la cadena $M_k$ y varios pares $(a, b)$, cuál es la subcadena de $M_k$ desde el carácter $a$-ésimo hasta el $b$-ésimo, inclusive. Escriba un programa que encuentre las respuestas a estas consultas.

Entrada

La primera línea contiene la cadena inicial $M_0$. La segunda línea contiene la cadena de reglas $S$.

Las cadenas de entrada satisfacen las siguientes condiciones:

• La longitud de cada cadena no es menor que 1 y no es mayor que $10^5$.
• Todos los caracteres en cada cadena tienen un valor de código ASCII entre 33 y 126, inclusive. Tenga en cuenta que no se incluyen espacios en blanco.
• $M_0$ no contiene ningún carácter "$" (código ASCII 36).
• $S$ contiene al menos un carácter "$" (código ASCII 36).

La tercera línea contiene dos enteros $k$ y $q$ ($1 \le k \le 10^5$, $1 \le q \le 10^5$).

Cada una de las siguientes $q$ líneas contiene una consulta: dos enteros $a_i$ y $b_i$ ($1 \le a_i \le b_i \le 10^{18}$, $b_i - a_i < 10^5$). Se garantiza que $b_i$ no excede la longitud de $M_k$.

Salida

Imprima $q$ líneas.

En la línea $i$, imprima un total de $b_i - a_i + 1$ caracteres: la subcadena de $M_k$ desde el carácter $a_i$-ésimo hasta el carácter $b_i$-ésimo inclusive.

Se garantiza que, en la respuesta correcta, el número total de caracteres impresos (excluyendo los saltos de línea) no excederá $5 \cdot 10^5$.

Ejemplos

Entrada 1

It’s_a_cat,_not_a_mango
It’s_"$",_not_"$"
1 6
1 20
18 35
49 61
29 40
41 50
5 5

Salida 1

It’s_"It’s_a_cat,_no
_not_a_mango",_not
_not_a_mango"
o",_not_"It’
s_a_cat,_n
_

Entrada 2

Ad_finitum
$
100000 4
1 10
1 2
4 10
5 8

Salida 2

Ad_finitum
Ad
finitum
init

Entrada 3

THE_END
$_IS_NEVER_$_IS_NEVER_$
88 5
1 7
3256 3257
67706 67710
111011 111017
999999999999999968 999999999999999993

Salida 3

THE_END
IS
NEVER
THE_END
_THE_END_IS_NEVER_THE_END_