题目描述

给定一个基础字符串 $M_0$ 和一个规则字符串 $S$。

对于每个正整数 $i$，字符串 $M_i$ 定义为：把 $S$ 中的每一个字符 $ 同时替换成完整的字符串 $M_{i-1}$。

例如，若

M0 = It's_a_cat,_not_a_mango
S  = It's_"$",_not_"$"

则 $M_1$ 是把 $S$ 中的两个 $ 都替换为 $M_0$ 后得到的字符串。

随着 $i$ 增大，$M_i$ 的长度可能极其庞大，因此无法直接构造整个字符串。你需要回答若干询问，每次输出 $M_k$ 的一个连续子串。

字符串下标从 $1$ 开始。

输入格式

第一行输入基础字符串 $M_0$。

第二行输入规则字符串 $S$。

两个字符串满足：

• 长度均在 $1$ 到 $10^5$ 之间；
• 每个字符的 ASCII 码在 $33$ 到 $126$ 之间，即均为可打印的非空白字符；
• $M_0$ 中不包含字符 $；
• $S$ 中至少包含一个字符 $。

第三行包含两个整数 $k,Q$。

接下来 $Q$ 行，第 $i$ 行包含两个整数 $a_i,b_i$。

保证

且所有询问输出长度之和满足

输出格式

对每个询问输出一行，为 $M_k$ 中从第 $a_i$ 个字符到第 $b_i$ 个字符的连续子串。

样例 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_