A+B Problem

Although da Vinci primarily worked as an artist, he was also well known for his scientific investigations rooting in nature. Da Vinci had outstanding skills in dividing natural phenomena into smaller segments to seek the secrets beyond the mystery, which involved a lot of mathematical computations.

While deriving the golden ratio and applying it in his artwork, da Vinci felt bored at repeating tedious computations, especially addition. He hoped that a calculator could compute the sum of two relatively large integers for him, however no one could implement an A+B algorithm in any programming language at his time.

Knowing that you have solved so many difficult problems at this programming contest, da Vinci was impressed by your problem-solving skills and asked if you could implement this A+B calculator for him. Because da Vinci wanted to compute incredibly large numbers, he decided to compress the integer A as N pairs of integers (t_i, d_i), where d_i is a digit and t_i is the number of times d_i repeats. In other words, A = d_1d_1...d_1 (repeats t_1 times) d_2d_2...d_2 (repeats t_2 times) ... d_Nd_N...d_N (repeats t_N times). B is compressed as M pairs of integers in the same way. The output of your program should also follow this format.

To make this format more standardized, no leading zero is allowed, t_i should be strictly positive, and d_i should not be equal to d_{i+1} (or they can be compressed as (t_i + t_{i+1}, d_i)). For example, the integer 1112231 should be encoded as (3, 1), (2, 2), (1, 3), (1, 1), but (1, 0), (3, 1), (2, 2), (1, 3), (1, 1) or (2, 1), (1, 1), (2, 2), (1, 3), (1, 1) or (3, 1), (0, 9), (2, 2), (1, 3), (1, 1) would be invalid.

The first line contains a number $1 \le K \le 20$, which is the number of input data sets in the file. This is followed by $K$ data sets of the following form:

The first line of each data set contains a single integer $1 \le N \le 100$, followed by $N$ lines describing number A. Each of the $N$ lines contains a pair of integers $1 \le t_i \le 10^{18}$, $0 \le d_i \le 9$ separated by space.

The following line contains a single integer $1 \le M \le 100$, followed by $M$ lines describing number B. Each of the $M$ lines contains a pair of integers $1 \le t_j \le 10^{18}$, $0 \le d_j \le 9$ separated by space.

It is guaranteed that the presentation of A and B is well-formed without leading zero, i.e. $\forall 2 \le i \le N$ (or $M$ for B), $d_{i-1} \ne d_i$ and $d_1 \ne 0$. Also, the input integers have at most $10^{18}$ digits after decoding, i.e. $(\sum t_i) \le 10^{18}$.

For each data set, first output “Data Set x:” on a line by itself, where x is its number. Then, output the sum of A + B in the same format as the input.

Each data set should be followed by a blank line

The first data set is 9999909999 + 999999 = 10000909998.

The second data set is 999...999 (44444 9's) 333...333 (55555 3's) + 111...111 (44444 1's) 777...777 (55555 7's) = 111...111 (99999 1's) 0.

The third data set is trivial, however it warns that you may want to use 8-byte integer types (long long in C/C++, long in Java), which can hold integers up to 9.22 × $10^{18}$.