A + B Problem#1729
Do you know the famous Fibonacci sequence? It is defined by the recurrence relation:
F_0 = 0, F_1 = 1, and F_n = F_{n-1} + F_{n-2} for n \geq 2.
The Fibonacci numbers have many interesting properties. One of them is that the Fibonacci numbers can be used to represent integers. Every positive integer has a unique representation of the form
n = F_{k_1} + F_{k_2} + \ldots + F_{k_m}, where k_i \geq k_{i-1} + 2 for 2 \leq i \leq m, and k_1 \geq 2.
For example, can be represented as F_2 + F_5 and as F_2 + F_4 + F_6.
Now that you know how to represent positive integers using Fibonacci numbers, can you add them? You are given two positive integers, each represented as a sum of distinct, non-consecutive Fibonacci numbers. Your task is to compute their sum, represented in the same way.
The first line contains a single integer , the number of test cases.
Each test case consists of two lines. Each line contains a single integer followed by integers k_1, k_2, \ldots, k_m, indicating a positive integer represented as F_{k_1} + F_{k_2} + \ldots + F_{k_m}.
It is guaranteed that the input is correct. 1 \leq T \leq 100, 1 \leq m \leq 100, 2 \leq k_i \leq 1000000.
For each test case, output the case number first, then on the next line output the sum of the two given numbers, represented as a sum of distinct, non-consecutive Fibonacci numbers, in the same format as the input.
Example 1