Mango là một chú mèo sống ở nhà bên cạnh. Cái tên này bắt nguồn từ việc màu lông của nó giống với màu của nước ép xoài. Tôi không biết liệu Mango có thích cái tên này hay không.

Giống như hầu hết các loài mèo, Mango rất dễ thương. Mango, chú mèo được nhiều người yêu mến, đôi khi trở thành chủ đề của những câu đùa hài hước như "Trông Mango ngon quá" hoặc "Đó là một con mèo, không phải một quả xoài". Gần đây, Mango đã trở thành nhân vật chính trong một meme về việc tạo ra các câu đệ quy sau đây.

Giả sử chúng ta có chuỗi ban đầu $M_0$ và chuỗi quy tắc $S$. Với bất kỳ số nguyên dương $i$ nào, $M_i$ được định nghĩa là chuỗi trong đó mỗi ký tự "$" được thay thế bằng chuỗi $M_{i-1}$.

Việc xây dựng một vài chuỗi đầu tiên rất dễ dàng. Ví dụ, nếu chúng ta nói $M_0$ là "That’s a cat, not a mango", và $S$ là "That’s a "$", not a "$"", thì $M_0$, $M_1$, và $M_2$ sẽ trông như sau:

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

Không chỉ $M_3$ và $M_4$, mà cả $M_{1000}$ cũng có thể được xây dựng theo cùng một nguyên tắc. Tuy nhiên, ngay cả $M_5$ cũng đã khá dài. Dù vậy, tôi tự hỏi, đối với chuỗi $M_k$ và một vài cặp $(a, b)$, chuỗi con của $M_k$ từ ký tự thứ $a$ đến thứ $b$ (bao gồm cả hai đầu) là gì. Hãy viết một chương trình tìm câu trả lời cho các truy vấn này.

Dữ liệu vào

Dòng đầu tiên chứa chuỗi ban đầu $M_0$. Dòng thứ hai chứa chuỗi quy tắc $S$.

Các chuỗi đầu vào thỏa mãn các điều kiện sau: Độ dài của mỗi chuỗi không nhỏ hơn 1 và không lớn hơn $10^5$. Tất cả các ký tự trong mỗi chuỗi có giá trị mã ASCII từ 33 đến 126, bao gồm cả hai đầu. Lưu ý rằng không bao gồm khoảng trắng. $M_0$ không chứa bất kỳ ký tự "$" (mã ASCII 36) nào. $S$ chứa ít nhất một ký tự "$" (mã ASCII 36).

Dòng thứ ba chứa hai số nguyên $k$ và $q$ ($1 \le k \le 10^5$, $1 \le q \le 10^5$). Mỗi dòng trong số $q$ dòng tiếp theo chứa một truy vấn: hai số nguyên $a_i$ và $b_i$ ($1 \le a_i \le b_i \le 10^{18}$, $b_i - a_i < 10^5$). Đảm bảo rằng $b_i$ không vượt quá độ dài của $M_k$.

Dữ liệu ra

In ra $q$ dòng. Trên dòng $i$, in ra tổng cộng $b_i - a_i + 1$ ký tự: chuỗi con của $M_k$ từ ký tự thứ $a_i$ đến ký tự thứ $b_i$ (bao gồm cả hai đầu).

Đảm bảo rằng, trong câu trả lời đúng, tổng số ký tự được in ra (không bao gồm ký tự xuống dòng) sẽ không vượt quá $5 \cdot 10^5$.

Ví dụ

Ví dụ 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
_

Ví dụ 2

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

Ad_finitum
Ad
finitum
init

Ví dụ 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_