I have been attempting this British Informatics Olympiad question for many weeks now. I tried creating all plans but this would time out very easily (and take too much memory in some cases). I tried finding first plan and then counting up but this too would time out. I checked the sample tests and the biggest numbers they had were around 2^43, so I am not sure if they want a solution much better than that. Any help would be much appreciated. A spy, currently working their way through an enemy compound, has been given a false plan. The plan is an ordered list of letters. In order to make the plan look realistic, the number of adjacent identical letters in the plan has been limited. For example, suppose that the plan contains four letters, each of which is an A or a B, and that there are never more than two adjacent identical letters. There are 10 possible plans: AABA AABB ABAA ABAB ABBA BAAB BABA BABB BBAA BBAB These have been listed in alphabetical order.

Write a program to determine the nth possible plan. Your program should input a line containing three integers p, q, r (1 ≤ p, q, r ≤ 12) indicating (in order) that the first p letters of the alphabet can be used, no more than q adjacent identical letters are permitted and that the plan should contain exactly r letters. You should then input a line containing a single number n (1 ≤ n < 2^63). You will only be given input where n is no greater than the number of possible plans. You should output the nth possible plan.

(Time limit = 1 second per test).

Sample run INPUT: 2 2 4 7

OUTPUT: BABA