Chưa ai chưa từng nghe qua cái tên Mandarin-chan. Đó là một vị đại hiệp đã từng làm mưa làm gió trong cộng đồng lập trình Việt Nam. Với tiểu sử khủng thứ 2 không ai dám nhận số 1 (top 5 CTF, TỰ LÀM full đề CSES, …), anh đã gieo nên nỗi khiếp sợ trong cộng đồng Tin học trong nước cũng như quốc tế. Mỗi lần cái tên Mandarin-chan được nhắc đến trong một cuộc hội thoại, mọi người ai ai cũng bủn rủn tay chân, ngộp thở, thở không được.

Với ảnh hưởng to lớn cùng với bảng thành tích dày cộp như thế, chắc hẳn các bạn đang thầm nghĩ: giới trẻ sẽ không tài nào bắt kịp được với trình độ vượt thời gian, vượt không gian, vượt mọi lẽ thường của Mandarin-chan. Và đúng thật như vậy, trải qua bao nhiêu năm, bao nhiêu thế hệ, người đến rồi lại đi, dù cho các bạn trẻ nhiệt huyết nay đã trở thành những bô lão hết xăng, không còn thiết tha với tin học nữa, thì ngài Mandarin-chan vẫn còn ở đó, vẫn còn bón hành cho bọn trẻ, thầm mong mình sẽ tìm được một truyền nhân thực thụ.

May mắn thay, một nhân tố X đã xuất hiện: Dark Phantom Horse (DPH). Dù học lập trình muộn hơn nhiều so với các bạn đồng trang lứa, chỉ trong vài tháng, DPH đã đạt được rank đỏ VNOJ - một thành tích vô tiền khoáng hậu, từ đó gây dựng tiếng vang lớn trong cộng đồng lập trình thi đấu. Nếu bây giờ bạn hỏi DPH sẽ chọn tình yêu hay sự nghiệp, thì cậu ấy sẽ lấy cả hai chứ vì sao phải chọn.

Tuy nhiên, đời đâu như mơ, đôi khi giỏi quá cũng đâu phải là tốt. Một kẻ xấu, với bí danh là Lime Quartz Horse (LQH), đã đột nhập vào hệ thống Codeforces, chép những bài mà DPH đã AC, rồi quay ngược về quá khứ và nộp những bài tập đó. Như thế, chàng trai DPH đã bị tố cáo chép code của LQH, và cậu đã mất hết mọi thứ. Mất vợ, mất con, mất người yêu, mất nick đỏ, mất thương hiệu. Cậu có buồn không? Có chứ, cay LQH nữa là đằng khác. Cậu không ngờ một người vô tội như cậu, một người đã gây dựng nên mọi thứ từ hai bàn tay trắng nay đã sạt nghiệp dưới tay LQH. DPH đành phải mượn rượu giải sầu và trong cơn ph… à nhầm cơn giận, chiếc bàn phím cơ 14 củ của DPH đã vỡ nát lúc nào không hay.

LQH rất hả hê trước sự sụp đổ của đế chế DPH, và đang chuẩn bị đi săn con mồi tiếp theo mà không biết rằng, DPH thực sự là một thiên tài không chỉ về Tin học mà còn về Chiến thuật. Sau nhiều giờ suy nghĩ, DPH cuối cùng cũng đã nấu được một kế hoạch hoàn hảo. Cậu ấy sẽ đột nhập vào cỗ máy thời gian của LQH, đem code của chính mình về quá khứ, trước khi LQH nộp code và nộp code trước. Khi đó, LQH mới được xem là kẻ chép code, vợ con, tiền tài sẽ trở về và đế chế của DPH sẽ lớn mạnh trở lại.

Cơ mà, bàn phím đã tan tành, DPH phải làm gì đây? Cậu ta nay đã không còn một xu dính túi để có thể mua bàn phím, để tiếp tục hành trình lập trình thi đấu của mình. Chính vì thế, cậu đành phải tìm đến bãi phế liệu, mong tìm được chiếc bàn phím còn hoạt động. Và cậu đã tìm thấy nó, một chiếc bàn phím xinh đẹp, còn hoạt động tốt (nhưng không biết có hoạt động đúng không).

DPH rất muốn đánh bại LQH, vậy nên bàn phím anh ấy không được phép sai, vì vậy anh ấy đã nhờ đến sự trợ giúp của bạn. Cách thử bàn phím của DPH diễn ra như sau:

• Đầu tiên, DPH chuẩn bị trước một xâu ~S~ (~|S| \leq 10^3~),
• Tiếp theo, DPH lần lượt thực hiện ~m~ (~m \leq 10^4~) thao tác. Trong thao tác thứ ~j~, DPH sẽ copy và dán ~S[l_j,r_j]~ vào cuối xâu S. Dữ liệu luôn đảm bào ~r_j \leq |S|~ vào thời điểm diễn ra thao tác thứ ~j~, và ~|S| \leq 10^{18}~ sau tất cả các thao tác.
• Cuối cùng, DPH hỏi bạn ~q~ (~q \leq 10^3~) truy vấn. Với truy vấn thứ ~k~, DPH yêu cầu bạn cho biết ~S[l_k,r_k]~. Dữ liệu đảm bảo ~ \displaystyle\sum_{k = 1}^q (r_k - l_k + 1) \leq 2*10^6~ và ~r_k \leq |S|~ sau tất cả các thao tác.

Chú thích: ~S[l, r]~ là kí hiệu cho xâu con ~S_lS_{l+1}S_{l+2}~…~S_r~ của ~S~,

DPH chỉ yêu cầu bạn in ra ~S[l, r]~ trong mỗi truy vấn, còn việc kiểm tra bàn phím với dữ liệu trên thì anh ấy sẽ tự làm. Vì việc rất cấp bách nên DPH không thể tự viết chương trình lúc này. Vì vậy bạn hãy giúp DPH viết một chương trình có thể xử lý các thao tác trên một cách đúng đắn nhé.

Input:

Dòng đầu tiên chứa xâu ~S~.

Dòng thứ hai gồm hai số nguyên dương ~m~, ~q~.

~m~ dòng tiếp theo, dòng thứ ~j~ gồm hai số nguyên dương ~l_j~, ~r_j~ thể hiện thao tác thứ ~j~.

~q~ dòng tiép theo, dòng thứ ~k~ gồm hai số nguyên dương ~l_k~, ~r_k~ thể hiện truy vấn thứ ~k~.

Output:

In ra kết quả của mỗi truy vấn.

Sample Input:

abv
2 2
1 3
2 5
1 10
3 6

Sample Output:

abvabvbvab
vabv

Giải thích test mẫu: Xâu S sau 2 thao tác sẽ biến đổi như dưới đây:

~abv~ -> ~abvabv~ -> ~abvabvbvab~.

Như vậy ~S[1, 10] = abvabvbvab~, ~S[3, 6] = vabv~.

• Subtask 1: (5% số điểm): Dữ liệu đầu vào đảm bảo rằng tổng ~(r_j - l_j + 1)~ của tất cả thao tác không vượt quá ~10^7~,
• Subtask 2: (15% số điểm): Dữ liệu đầu vào đảm bảo rằng tổng ~(r_k - l_k + 1)~ của tất cả truy vấn không vượt quá ~10^4~,
• Subtask 3: (80% số điểm): Không có ràng buộc gì thêm.