망고는 옆집에 사는 고양이입니다. 이름은 망고 주스와 비슷한 색깔에서 유래했습니다. 망고가 이 이름을 좋아하는지는 잘 모르겠습니다.
대부분의 고양이처럼 망고는 귀엽습니다. 많은 사람이 좋아하는 망고는 가끔 "망고가 맛있어 보인다"거나 "저건 고양이지 망고가 아니다"와 같은 유머러스한 농담의 소재가 되기도 합니다. 최근 망고는 다음과 같은 재귀적 문장 생성에 관한 밈의 주인공이 되었습니다.
초기 문자열 $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$번째 문자까지(양 끝 포함)의 부분 문자열이 무엇인지 궁금합니다. 이러한 쿼리에 대한 답을 찾는 프로그램을 작성하세요.
입력
첫 번째 줄에는 초기 문자열 $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
출력 1
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
출력 2
Ad_finitum Ad finitum init
입력 3
THE_END $_IS_NEVER_$_IS_NEVER_$ 88 5 1 7 3256 3257 67706 67710 111011 111017 999999999999999968 999999999999999993
출력 3
THE_END IS NEVER THE_END _THE_END_IS_NEVER_THE_END_