찾아 바꾸기

Bessie는 최신 텍스트 편집 프로그램 miV를 쓰고 있다. 이 프로그램의 찾아 바꾸기 기능으로 소문자 영어 알파벳 $c$가 나타나는 곳을 모두 찾아, 각각을 비어 있지 않은 소문자 문자열 $s$로 바꿀 수 있다. 예를 들어 문자열 "ball"에서 $c$를 'l', $s$를 "na"로 고르면 문자열은 "banana"가 된다.

Bessie는 문자열 "a"에서 시작해 이 연산을 여러 번 적용하여 최종 문자열 $S$를 얻는다. $S$는 매우 길 수 있으므로, 주어진 $l$과 $r$ ($1\le l\le r\le \min(|S|,10^{18})$)에 대해 $l$번째 문자부터 $r$번째 문자까지의 부분 문자열 $S_{l\dots r}$을 구하려 한다.

모든 연산에서 $|s|$의 합은 $2\cdot 10^5$ 이하이며, $r-l+1\le 2\cdot 10^5$이다.

첫 줄에 $l$, $r$, 연산의 개수가 주어진다. 이어지는 각 줄에는 연산 하나를 나타내는 $c$와 $s$가 주어진다. 모든 문자는 'a'부터 'z'까지의 소문자 영어 알파벳이다.

부분 문자열 $S_{l\dots r}$을 한 줄에 출력한다.

문자열은 다음과 같이 바뀐다.

a $\rightarrow$ ab $\rightarrow$ bcb $\rightarrow$ bdeb $\rightarrow$ bbbdebbb