A+B 문제

다빈치는 주로 예술가로 활동했지만, 자연을 탐구하는 과학적 연구로도 이름이 높았다. 다빈치는 자연 현상을 작은 단위로 나누어 그 너머의 비밀을 파헤치는 데 뛰어난 재능을 보였고, 그 과정에는 많은 수학적 계산이 따랐다.

황금비를 유도하고 그것을 작품에 적용하던 다빈치는 지루한 계산, 특히 덧셈을 반복하는 데 싫증을 느꼈다. 그는 계산기가 비교적 큰 두 정수의 합을 대신 구해 주기를 바랐지만, 당시에는 어떤 프로그래밍 언어로도 A+B 알고리즘을 구현할 수 있는 사람이 없었다.

이 프로그래밍 대회에서 어려운 문제를 많이 풀어 왔다는 소식을 들은 다빈치는 여러분의 문제 해결 능력에 감탄하고, 이 A+B 계산기를 구현해 달라고 부탁했다. 다빈치는 믿기 힘들 만큼 큰 수를 계산하고 싶었기에, 정수 A를 N개의 정수 쌍 (t_i, d_i)로 압축하기로 했다. 여기서 d_i는 숫자이고 t_i는 d_i가 반복되는 횟수이다. 다시 말해 A = d_1d_1...d_1 (t_1번 반복) d_2d_2...d_2 (t_2번 반복) ... d_Nd_N...d_N (t_N번 반복)이다. B도 같은 방식으로 M개의 정수 쌍으로 압축된다. 프로그램의 출력도 이 형식을 따라야 한다.

이 형식을 더 표준화하기 위해 앞에 오는 0은 허용되지 않고, t_i는 반드시 양수이며, d_i는 d_{i+1}과 같으면 안 된다 (같다면 (t_i + t_{i+1}, d_i)로 압축할 수 있다). 예를 들어 정수 1112231은 (3, 1), (2, 2), (1, 3), (1, 1)로 인코딩해야 하지만, (1, 0), (3, 1), (2, 2), (1, 3), (1, 1)이나 (2, 1), (1, 1), (2, 2), (1, 3), (1, 1)이나 (3, 1), (0, 9), (2, 2), (1, 3), (1, 1)은 유효하지 않다.

첫 줄에 파일에 들어 있는 입력 데이터 세트의 수 $1 \le K \le 20$이 주어진다. 이어서 다음 형식의 데이터 세트 $K$개가 주어진다.

각 데이터 세트의 첫 줄에는 정수 $1 \le N \le 100$이 주어지고, 이어서 수 A를 설명하는 $N$개의 줄이 주어진다. $N$개의 줄 각각에는 공백으로 구분된 정수 쌍 $1 \le t_i \le 10^{18}$, $0 \le d_i \le 9$가 주어진다.

다음 줄에는 정수 $1 \le M \le 100$이 주어지고, 이어서 수 B를 설명하는 $M$개의 줄이 주어진다. $M$개의 줄 각각에는 공백으로 구분된 정수 쌍 $1 \le t_j \le 10^{18}$, $0 \le d_j \le 9$가 주어진다.

A와 B의 표현은 앞에 오는 0 없이 올바르게 주어진다. 즉 $\forall 2 \le i \le N$ (B의 경우 $M$), $d_{i-1} \ne d_i$이고 $d_1 \ne 0$이다. 또한 입력으로 주어지는 정수는 복호화한 뒤 최대 $10^{18}$자리이며, 즉 $(\sum t_i) \le 10^{18}$이다.

각 데이터 세트마다 먼저 “Data Set x:”를 한 줄에 출력한다. 여기서 x는 데이터 세트의 번호이다. 그다음 A + B의 합을 입력과 같은 형식으로 출력한다.

각 데이터 세트 뒤에는 빈 줄을 출력한다.

첫 번째 데이터 세트는 9999909999 + 999999 = 10000909998이다.

두 번째 데이터 세트는 999...999 (9가 44444개) 333...333 (3이 55555개) + 111...111 (1이 44444개) 777...777 (7이 55555개) = 111...111 (1이 99999개) 0이다.

세 번째 데이터 세트는 자명하지만, 8바이트 정수형 (C/C++의 long long, Java의 long)을 쓰고 싶어질 수 있다는 점을 알려 준다. 이들은 최대 9.22 × $10^{18}$까지의 정수를 담을 수 있다.