Mango 是一只住在隔壁的猫。它的名字来源于它的颜色与芒果汁的颜色相似。我不知道 Mango 是否喜欢这个名字。

像大多数猫一样，Mango 很可爱。许多人都喜欢的 Mango 有时会成为幽默笑话的主题，比如“这只芒果看起来很好吃”或“那是一只猫，不是芒果”。最近，Mango 成为了一个关于生成以下递归句子的梗的主角。

假设我们有一个初始字符串 $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)$，从第 $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

样例输出 1

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

样例输出 2

Ad_finitum
Ad
finitum
init

样例输入 3

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

样例输出 3

THE_END
IS
NEVER
THE_END
_THE_END_IS_NEVER_THE_END_