Mango to kot, który mieszka po sąsiedzku. Jego imię pochodzi od faktu, że jego kolor przypomina kolor soku z mango. Nie wiem, czy Mango lubi to imię.

Jak większość kotów, Mango jest uroczy. Mango, którego wiele osób lubi, czasami staje się przedmiotem humorystycznych żartów, takich jak „Mango wygląda smakowicie” lub „To kot, a nie mango”. Ostatnio Mango stał się bohaterem mema dotyczącego generowania następujących rekurencyjnych zdań.

Załóżmy, że mamy początkowy ciąg $M_0$ oraz ciąg reguły $S$. Dla każdej liczby całkowitej dodatniej $i$, $M_i$ jest zdefiniowany jako ciąg, w którym każdy znak „$” jest zastąpiony ciągiem $M_{i-1}$.

Łatwo jest skonstruować kilka pierwszych takich ciągów. Na przykład, jeśli przyjmiemy, że $M_0$ to „That’s a cat, not a mango”, a $S$ to „That’s a "$", not a "$"”, to $M_0$, $M_1$ oraz $M_2$ wyglądają następująco:

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

Nie tylko $M_3$ i $M_4$, ale także $M_{1000}$ można skonstruować przy użyciu tej samej zasady. Jednak nawet $M_5$ jest już dość długi. Mimo to, zastanawiam się, dla ciągu $M_k$ oraz kilku par $(a, b)$, jaki jest podciąg $M_k$ od $a$-tego do $b$-tego znaku włącznie. Napisz program, który znajdzie odpowiedzi na te zapytania.

Wejście

Pierwsza linia zawiera początkowy ciąg $M_0$. Druga linia zawiera ciąg reguły $S$.

Ciągi wejściowe spełniają następujące warunki: Długość każdego ciągu nie jest mniejsza niż 1 i nie większa niż $10^5$. Wszystkie znaki w każdym ciągu mają kod ASCII z zakresu od 33 do 126 włącznie. Zauważ, że znaki białe nie są uwzględnione. $M_0$ nie zawiera żadnych znaków „$” (kod ASCII 36). $S$ zawiera co najmniej jeden znak „$” (kod ASCII 36).

Trzecia linia zawiera dwie liczby całkowite $k$ oraz $q$ ($1 \le k \le 10^5$, $1 \le q \le 10^5$). Każda z następnych $q$ linii zawiera zapytanie: dwie liczby całkowite $a_i$ oraz $b_i$ ($1 \le a_i \le b_i \le 10^{18}$, $b_i - a_i < 10^5$). Gwarantuje się, że $b_i$ nie przekracza długości $M_k$.

Wyjście

Wypisz $q$ linii. W linii $i$ wypisz łącznie $b_i - a_i + 1$ znaków: podciąg $M_k$ od $a_i$-tego znaku do $b_i$-tego znaku włącznie.

Gwarantuje się, że w poprawnej odpowiedzi łączna liczba wypisanych znaków (nie licząc znaków końca linii) nie przekroczy $5 \cdot 10^5$.

Przykład

Wejście 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

Wyjście 1

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

Wejście 2

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

Wyjście 2

Ad_finitum
Ad
finitum
init

Wejście 3

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

Wyjście 3

THE_END
IS
NEVER
THE_END
_THE_END_IS_NEVER_THE_END_