Competitions

# Fibonacci Strings

Fibonacci sequence of strings is defined as follows: s1 = b, s2 = a, sk = sk-1 + sk-2 for k > 2. For example, s3 = ab, s4 = aba, s5 = abaab and etc.

Given positive integers n, m, l. Print the substring of sn which starts at position m and have the length l.

#### Input

One line contains three space-separated positive integers n, m and l, where 1n40; 1mlength(Sn), 1l1000.

#### Output

Print the substring of sn which starts at position m and have the length l (the length of the printed substring may be less if the length of the remainder of the string sn, starting from position m, is less than l).

Time limit 1 second
Memory limit 128 MiB
Input example #1
5 3 2

Output example #1
aa

Input example #2
5 3 10

Output example #2
aab