Mango は隣の家に住んでいる猫である。その名前は、色がマンゴージュースの色に似ていることに由来する。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)$ が与えられたとき、$M_k$ の $a$ 文字目から $b$ 文字目まで（両端を含む）の文字列が何であるかを知りたい。これらのクエリに対する答えを見つけるプログラムを作成せよ。

入力

1行目には初期文字列 $M_0$ が含まれる。 2行目にはルール文字列 $S$ が含まれる。 入力文字列は以下の条件を満たす。

• 各文字列の長さは 1 以上 $10^5$ 以下である。
• 各文字列のすべての文字は、ASCII コード値が 33 から 126 の範囲内である。空白文字は含まれないことに注意せよ。
• $M_0$ には「$」（ASCII コード 36）という文字は含まれない。
• $S$ には少なくとも 1 つの「$」（ASCII コード 36）という文字が含まれる。

3行目には 2 つの整数 $k$ と $q$ ($1 \le k \le 10^5, 1 \le q \le 10^5$) が含まれる。 続く $q$ 行の各行には、クエリとして 2 つの整数 $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_