Манго — это кот, который живет по соседству. Имя появилось из-за того, что его цвет похож на цвет мангового сока. Я не знаю, нравится ли Манго это имя.

Как и большинство котов, Манго милый. Манго, который многим нравится, иногда становится предметом шуток, таких как «Манго выглядит аппетитно» или «Это кот, а не манго». Недавно Манго стал героем мема о создании следующих рекурсивных предложений.

Пусть у нас есть начальная строка $M_0$ и строка правил $S$. Для любого целого положительного числа $i$, $M_i$ определяется как строка, в которой каждый символ «$» заменен на строку $M_{i-1}$.

Легко построить первые несколько таких строк. Например, если мы скажем, что $M_0$ — это «That’s a cat, not a mango», а $S$ — это «That’s a "$", not a "$"», то $M_0$, $M_1$ и $M_2$ будут выглядеть следующим образом:

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

Не только $M_3$ и $M_4$, но и $M_{1000}$ можно построить по тому же принципу. Однако даже $M_5$ уже довольно длинная. Тем не менее, мне интересно, для строки $M_k$ и нескольких пар $(a, b)$, какой будет подстрока $M_k$ с $a$-го по $b$-й символ включительно. Напишите программу, которая находит ответы на эти запросы.

Входные данные

Первая строка содержит начальную строку $M_0$. Вторая строка содержит строку правил $S$.

Входные строки удовлетворяют следующим условиям: Длина каждой строки не менее 1 и не более $10^5$. Все символы в каждой строке имеют код ASCII от 33 до 126 включительно. Обратите внимание, что пробельные символы не включены. $M_0$ не содержит символов «$» (код ASCII 36). $S$ содержит хотя бы один символ «$» (код ASCII 36).

Третья строка содержит два целых числа $k$ и $q$ ($1 \le k \le 10^5$, $1 \le q \le 10^5$). Каждая из следующих $q$ строк содержит запрос: два целых числа $a_i$ и $b_i$ ($1 \le a_i \le b_i \le 10^{18}$, $b_i - a_i < 10^5$). Гарантируется, что $b_i$ не превышает длину $M_k$.

Выходные данные

Выведите $q$ строк. В $i$-й строке выведите в общей сложности $b_i - a_i + 1$ символ: подстроку $M_k$ с $a_i$-го по $b_i$-й символ включительно.

Гарантируется, что в правильном ответе общее количество выведенных символов (без учета символов переноса строки) не превысит $5 \cdot 10^5$.

Примеры

Примеры 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

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

Примеры 2

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

Ad_finitum
Ad
finitum
init

Примеры 3

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

THE_END
IS
NEVER
THE_END
_THE_END_IS_NEVER_THE_END_