그건 망고가 아니라 고양이예요

망고는 이하의 집에 사는 고양이이다. 이름은 집에 있던 망고주스와 색깔이 비슷해서 붙었다. 망고가 이 이름을 마음에 들어 하는지는 알 수 없다.

삶은 힘들지만 고양이는 귀엽다. 그래서 몇몇 사람들은 망고를 칭송하기도 하고, '망고가 얼망고?' 같은 말장난을 하거나 '망고 맛있겠다' 같은 중의적인 농담을 하기도 한다. 이하는 망고가 망고라고 주장하지만, 몇몇 사람들은 '그건 망고가 아니라 고양이예요'라고 말하게 되었다. 이하는 이 일을 계기로 PS 문제를 만들기로 했다.

기본 문자열 $M\_0$와 규칙 문자열 $S$가 있다고 하자. 이때 양의 정수 $i$에 대해 $M\_i$는 $S$에 있는 모든 $ 문자를 문자열 $M\_{i-1}$로 바꾼 문자열로 정의한다. 문자열이 길지 않다면 몇 개는 손으로 만들어 볼 수 있다. $M\_0$을 그건 망고가 아니라 고양이예요, $S$를 그건 "$"가 아니라 "$"예요라고 하면 $M\_0$, $M\_1$, $M\_2$는 다음과 같다.

• $M\_0$ : 그건 망고가 아니라 고양이예요
• $M\_1$ : 그건 "그건 망고가 아니라 고양이예요"가 아니라 "그건 망고가 아니라 고양이예요"예요
• $M\_2$ : 그건 "그건 "그건 망고가 아니라 고양이예요"가 아니라 "그건 망고가 아니라 고양이예요"예요"가 아니라 "그건 "그건 망고가 아니라 고양이예요"가 아니라 "그건 망고가 아니라 고양이예요"예요"예요

$M\_3$, $M\_4$뿐만 아니라 $M\_{1\ 000}$도 같은 원리로 만들 수 있다. 다만 문자열 길이가 너무 길어질 수 있어서 보통은 전체를 만들 수 없다. 그렇다고 전체가 꼭 필요하지는 않다. 이하는 이렇게 생성되는 문자열의 연속한 부분을 구하려고 한다.

첫 번째 줄에는 기본 문자열 $M\_0$가, 두 번째 줄에는 규칙 문자열 $S$가 주어진다. 입력 문자열은 다음 조건을 만족한다.

• 각 문자열의 길이는 $1$ 이상 $10^5$ 이하이다.
• 각 문자열의 모든 문자는 줄바꿈을 제외하고 ASCII 코드 값이 33 이상 126 이하이다. 즉, 제어 문자(control character)가 아닌 출력 가능한 문자(printable character)로만 이루어져 있다.
• $M\_0$에는 $ (ASCII 코드 36) 문자가 없다.
• $S$에는 $ (ASCII 코드 36) 문자가 최소 하나 있다.

세 번째 줄에는 두 양의 정수 $k$와 $Q$가 공백으로 구분되어 주어진다. ($1 \leq k \leq 10^5$, $1 \leq Q \leq 10^5$)

네 번째 줄부터 $Q$개의 줄에 걸쳐 질의가 주어진다. 이 중 $i$번째 줄에는 두 정수 $a\_i$와 $b\_i$가 공백으로 구분되어 주어진다. ($1 \leq a\_i \leq b\_i \leq 10^{18}$, $b\_i - a\_i < 10^5$)

$b\_i$는 $M\_k$의 길이를 넘지 않으며, $b\_i - a\_i + 1$의 합은 $5 \times 10^5$을 넘지 않는다.

$Q$개의 줄에 걸쳐 $M\_k$의 부분 문자열을 출력한다. $i$번째 줄에는 $M\_k$의 $a\_i$번째 글자부터 $b\_i$번째 글자까지, 총 $b\_i-a\_i+1$개의 문자를 출력한다.