RLE 문자열 치환

어떤 프로그래밍 언어의 소스 코드는 대문자 알파벳만으로 이루어지고, 같은 문자가 길게 이어지는 일이 많다. 그래서 아주 큰 소스 코드를 다룰 때는 런 렝스 부호화로 압축해서 보관한다.

런 렝스 부호화(RLE)는 같은 문자가 이어지는 극대 구간마다 그 문자와 구간의 길이를 한 쌍으로 적는 압축 방식이다. 예를 들어 문자열 RRRRLEEE는 RLE로 R4L1E3이 된다.

RLE로 압축된 문자열 $A$, $B$, $C$가 주어진다. $A$의 부분 문자열로 $B$가 처음 나타나는 곳을 $C$로 바꾼 문자열을 RLE로 출력하는 프로그램을 작성하라. $A$에 $B$가 나타나지 않으면 $A$를 그대로 RLE로 출력한다.

입력은 세 줄이다.

A
B
C

세 줄은 RLE로 압축된 문자열 $A$, $B$, $C$를 차례로 나타내고, 각 줄의 형식은 다음과 같다.

c1 l1 c2 l2 ... cn ln $

$c_i$ ($1 \le i \le n$)는 대문자 알파벳(A부터 Z)이고, $l_i$ ($1 \le i \le n$, $1 \le l_i \le 10^8$)는 문자 $c_i$가 이어지는 길이를 나타내는 정수다. 쌍의 개수 $n$은 $1 \le n \le 10^3$을 만족한다. 문자와 정수는 공백 하나로 구분되고, 줄의 끝에는 종료 기호 $가 온다. $1 \le i \le n-1$을 만족하는 모든 $i$에 대해 $c_i \neq c_{i+1}$이 성립한다.

$A$에 $B$가 나타나면 처음 나타나는 $B$를 $C$로 바꾼 문자열을, 나타나지 않으면 $A$를 그대로 RLE로 압축해 다음 형식으로 한 줄에 출력한다.

c1 l1 c2 l2 ... cm lm $

$1 \le i \le m-1$에 대해 $c_i \neq c_{i+1}$이어야 하고, $1 \le i \le m$에 대해 $l_i > 0$이어야 한다.