H - RLE Replacement

Problem Statement

In JAG Kingdom, ICPC (Intentionally Compressible Programming Code) is one of the common programming languages. Programs in this language only contain uppercase English letters and the same letters often appear repeatedly in ICPC programs. Thus, programmers in JAG Kingdom prefer to compress ICPC programs by Run Length Encoding in order to manage very large-scale ICPC programs.

Run Length Encoding (RLE) is a string compression method such that each maximal sequence of the same letters is encoded by a pair of the letter and the length. For example, the string "RRRRLEEE" is represented as "R4L1E3" in RLE.

Now, you manage many ICPC programs encoded by RLE. You are developing an editor for ICPC programs encoded by RLE, and now you would like to implement a replacement function. Given three strings $A$, $B$, and $C$ that are encoded by RLE, your task is to implement a function replacing the first occurrence of the substring $B$ in $A$ with $C$, and outputting the edited string encoded by RLE. If $B$ does not occur in $A$, you must output $A$ encoded by RLE without changes.

Input

The input consists of three lines.

> $A$
>  $B$
>  $C$

The lines represent strings $A$, $B$, and $C$ that are encoded by RLE, respectively. Each of the lines has the following format:

> $c_1$ $l_1$ $c_2$ $l_2$ $\ldots$ $c_n$ $l_n$ \$

Each $c_i$ ($1 \leq i \leq n$) is an uppercase English letter (`A`-`Z`) and $l_i$ ($1 \leq i \leq n$, $1 \leq l_i \leq 10^8$) is an integer which represents the length of the repetition of $c_i$. The number $n$ of the pairs of a letter and an integer satisfies $1 \leq n \leq 10^3$. A terminal symbol `$` indicates the end of a string encoded by RLE. The letters and the integers are separated by a single space. It is guaranteed that $c_i \neq c_{i+1}$ holds for any $1 \leq i \leq n-1$.

Output

Replace the first occurrence of the substring $B$ in $A$ with $C$ if $B$ occurs in $A$, and output the string encoded by RLE. The output must have the following format:

> $c_1$ $l_1$ $c_2$ $l_2$ $\ldots$ $c_m$ $l_m$ \$

Here, $c_i \neq c_{i+1}$ for $1 \leq i \leq m-1$ and $l_i \gt 0$ for $1 \leq i \leq m$ must hold.

Sample Input 1


R 100 L 20 E 10 \$
R 5 L 10 \$
X 20 \$

Output for the Sample Input 1


R 95 X 20 L 10 E 10 \$

Sample Input 2


A 3 B 3 A 3 \$
A 1 B 3 A 1 \$
A 2 \$

Output for the Sample Input 2


A 6 \$





Example

Input

R 100 L 20 E 10 \$
R 5 L 10 \$
X 20 \$


Output

R 95 X 20 L 10 E 10 \$

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def main():

	def inp():
		s = LS()
		a = []
		for i in range(len(s) - 1):
			if i % 2 == 0:
				a.append(s[i])
			else:
				a.append(int(s[i]))
		return a

	def com(a):
		r = a[:2]
		for i in range(2, len(a), 2):
			if a[i] == r[-2]:
				r[-1] += a[i + 1]
			else:
				r += a[i:i + 2]
		return r
	a = com(inp())
	b = com(inp())
	c = com(inp())
	r = []
	ff = True
	if len(b) == 2:
		b0 = b[0]
		b1 = b[1]
		for i in range(0, len(a), 2):
			if a[i] == b0:
				while a[i + 1] >= b1 and ff:
					r += c
					a[i + 1] -= b1
					ff = False
				if a[i + 1] > 0:
					r += a[i:i + 2]
			else:
				r += a[i:i + 2]
	else:
		i = 0
		al = len(a)
		bl = len(b)
		be = bl - 2
		while i < al:
			f = True
			for j in range(0, bl, 2):
				ii = i + j
				if al <= ii or a[ii] != b[j] or (a[ii + 1] < b[j + 1] if j in [0, be] else a[ii + 1] != b[j + 1]) or (not ff):
					f = False
					break
			if f:
				for j in range(0, bl, 2):
					ii = i + j
					a[ii + 1] -= b[j + 1]
			if a[i + 1] > 0:
				r += a[i:i + 2]
			if f:
				r += c
				ff = False
			i += 2
	r += '$'
	return ' '.join(map(str, com(r)))
print(main())