Mango est un chat qui vit dans la maison d'à côté. Son nom vient du fait que sa couleur est similaire à celle du jus de mangue. Je ne sais pas si Mango aime ce nom.

Comme la plupart des chats, Mango est mignon. Mango, que beaucoup de gens apprécient, devient parfois le sujet de blagues humoristiques telles que « Le Mango a l'air délicieux » ou « C'est un chat, pas une mangue ». Récemment, Mango est devenu le héros d'un mème sur la génération des phrases récursives suivantes.

Supposons que nous ayons une chaîne initiale $M_0$ et une chaîne de règle $S$. Pour tout entier positif $i$, $M_i$ est définie comme la chaîne dans laquelle chaque caractère « $ » est remplacé par la chaîne $M_{i-1}$.

Il est facile de construire les premières chaînes de ce type. Par exemple, si nous disons que $M_0$ est « That’s a cat, not a mango » et que $S$ est « That’s a "$", not a "$" », alors $M_0$, $M_1$ et $M_2$ ressemblent à ceci :

• $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"" ».

Non seulement $M_3$ et $M_4$, mais aussi $M_{1000}$ peuvent être construits en utilisant le même principe. Cependant, même $M_5$ est déjà assez long. Pourtant, je me demande, pour la chaîne $M_k$ et plusieurs paires $(a, b)$, quelle est la sous-chaîne de $M_k$ allant du $a$-ième au $b$-ième caractère, inclus. Écrivez un programme qui trouve les réponses à ces requêtes.

Entrée

La première ligne contient la chaîne initiale $M_0$. La deuxième ligne contient la chaîne de règle $S$. Les chaînes d'entrée satisfont les conditions suivantes :

• La longueur de chaque chaîne n'est pas inférieure à 1 et pas supérieure à $10^5$.
• Tous les caractères de chaque chaîne ont une valeur de code ASCII comprise entre 33 et 126, inclus. Notez que les espaces ne sont pas inclus.
• $M_0$ ne contient aucun caractère « $ » (code ASCII 36).
• $S$ contient au moins un caractère « $ » (code ASCII 36).

La troisième ligne contient deux entiers $k$ et $q$ ($1 \le k \le 10^5$, $1 \le q \le 10^5$). Chacune des $q$ lignes suivantes contient une requête : deux entiers $a_i$ et $b_i$ ($1 \le a_i \le b_i \le 10^{18}$, $b_i - a_i < 10^5$). Il est garanti que $b_i$ ne dépasse pas la longueur de $M_k$.

Sortie

Imprimez $q$ lignes. Sur la ligne $i$, imprimez un total de $b_i - a_i + 1$ caractères : la sous-chaîne de $M_k$ du $a_i$-ième caractère au $b_i$-ième caractère inclus.

Il est garanti que, dans la réponse correcte, le nombre total de caractères imprimés (à l'exclusion des sauts de ligne) ne dépassera pas $5 \cdot 10^5$.

Exemples

Entrée 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

Sortie 1

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

Entrée 2

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

Sortie 2

Ad_finitum
Ad
finitum
init

Entrée 3

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

Sortie 3

THE_END
IS
NEVER
THE_END
_THE_END_IS_NEVER_THE_END_