Do you know the famous Fibonacci sequence? It is defined by the recurrence
F0 = 0, F1 = 1 and Fn = Fn-1 + Fn-2 for n ≥ 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 = Fk1 + Fk2 + … + Fkm, ki ≥ ki-1 + 2 for 2 ≤ i ≤ m and k1 ≥ 2
For example, 6 can be represented as F2+F5 and 12 can be represented as F2+F4+F6.
Now you know how to represent positive integers with the Fibonacci numbers, can you add them? Given two Fibonacci formed integers, you should calculate the sum of them.