#icpc2014springh. [icpc2014spring_h]RLE Replacement

[icpc2014spring_h]RLE Replacement

MathJax.Hub.Config({ tex2jax: { inlineMath: [["","",""], ["\\(","\\)"]], processEscapes: true }}); blockquote { font-family: Menlo, Monaco, "Courier New", monospace; color: #333333; display: block; padding: 8.5px; margin: 0 0 9px; font-size: 12px; line-height: 18px; background-color: #f5f5f5; border: 1px solid #ccc; border: 1px solid rgba(0, 0, 0, 0.15); -webkit-border-radius: 4px; -moz-border-radius: 4px; border-radius: 4px; white-space: pre; white-space: pre-wrap; word-break: break-all; word-wrap: break-word; }

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 AA, BB, and CC that are encoded by RLE, your task is to implement a function replacing the first occurrence of the substring BB in AA with CC, and outputting the edited string encoded by RLE. If BB does not occur in AA, you must output AA encoded by RLE without changes.


Input

The input consists of three lines.

AA
BB
CC

The lines represent strings AA, BB, and CC that are encoded by RLE, respectively. Each of the lines has the following format:

c_1c\_1 l_1l\_1 c_2c\_2 l_2l\_2 ldots\\ldots c_nc\_n l_nl\_n \$

Each c_ic\_i (1leqileqn1 \\leq i \\leq n) is an uppercase English letter (A-Z) and l_il\_i (1leqileqn1 \\leq i \\leq n, 1leql_ileq1081 \\leq l\_i \\leq 10^8) is an integer which represents the length of the repetition of c_ic\_i. The number nn of the pairs of a letter and an integer satisfies 1leqnleq1031 \\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_ineqc_i+1c\_i \\neq c\_{i+1} holds for any 1leqileqn11 \\leq i \\leq n-1.

Output

Replace the first occurrence of the substring BB in AA with CC if BB occurs in AA, and output the string encoded by RLE. The output must have the following format:

c_1c\_1 l_1l\_1 c_2c\_2 l_2l\_2 ldots\\ldots c_mc\_m l_ml\_m \$

Here, c_ineqc_i+1c\_i \\neq c\_{i+1} for 1leqileqm11 \\leq i \\leq m-1 and l_igt0l\_i \\gt 0 for 1leqileqm1 \\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

```plain
R 95 X 20 L 10 E 10 $```

* * *

### Sample Input 2

```plain
A 3 B 3 A 3 $
A 1 B 3 A 1 $
A 2 $```

### Output for the Sample Input 2

```plain
A 6 $```

* * *

### Source Name

[Japan Alumni Group Spring Contest 2014](http://acm-icpc.aitea.net/index.php?2013%2FPractice%2F%BD%D5%A5%B3%A5%F3%A5%C6%A5%B9%A5%C8%2F%B0%C6%C6%E2)

* * *