Mango 是一隻住在隔壁的貓。這個名字源於牠的顏色與芒果汁相似。我不知道 Mango 是否喜歡這個名字。

像大多數貓一樣，Mango 很可愛。許多人都喜歡 Mango，牠有時會成為幽默笑話的主題，例如「這隻芒果看起來很好吃」或「那是一隻貓，不是芒果」。最近，Mango 成為了一個關於生成以下遞迴句子的迷因主角。

假設我們有一個初始字串 $M_0$ 和一個規則字串 $S$。對於任何正整數 $i$，$M_i$ 定義為將 $S$ 中的每個「$」字元替換為字串 $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

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_