레이팅 미적용베시는 텍스트 편집 소프트웨어의 최신 최고 혁신인 miV를 사용하고 있다! 그 강력한 찾아 바꾸기 기능을 사용하면 영어 소문자 \(c\)의 모든 출현을 찾아 각각을 비어 있지 않은 소문자 문자열 \(s\)로 바꿀 수 있다. 예를 들어 문자열 "\(\texttt{ball}\)"에서 베시가 \(c\)를 'l'로, \(s\)를 "\(\texttt{na}\)"로 선택하면, 주어진 문자열은 "\(\texttt{banana}\)"로 변환된다.
베시는 문자열 "\(\texttt{a}\)"에서 시작해 이러한 찾아 바꾸기 연산을 여러 번 적용하여 최종 문자열 \(S\)를 만든다. \(S\)는 매우 클 수 있으므로, 그녀는 \(1\le l\le r\le \min(|S|,10^{18})\)인 \(l\)과 \(r\)이 주어질 때 \(S_{l\dots r}\) (\(S\)의 \(l\)번째 문자부터 \(r\)번째 문자까지의 부분 문자열)가 무엇인지 알고 싶어 한다.
모든 연산에 대한 \(|s|\)의 합이 \(2\cdot 10^5\) 이하이고, \(r-l+1\le 2\cdot 10^5\)임이 보장된다.
Problem credits: Benjamin Qi
채점 방식
- 입력 2-7: \(\sum |s|, r-l+1\le 2000\)
- 입력 8-15: 추가 제약이 없다.
Problem credits: Benjamin Qi
첫째 줄에 \(l\), \(r\), 그리고 연산의 수가 주어진다.
이후 각 줄은 연산 하나를 설명하며, 그 연산의 \(c\)와 \(s\)가 주어진다. 모든 문자는 'a'부터 'z'까지의 범위에 있다.
문자열 \(S_{l\dots r}\)를 한 줄에 출력한다.
3 8 4
a ab
a bc
c de
b bbbbdebbbThe string is transformed as follows:
$$ \texttt{a} \rightarrow \texttt{ab} \rightarrow \texttt{bcb} \rightarrow \texttt{bdeb} \rightarrow \texttt{bbbdebbb} $$