In what concerns the continuous evaluation solving exercises grade during the semester, you should submit until 23:59 of November 9th
(this exercise will still be available for submission after that deadline, but without counting towards your grade)
[to understand the context of this problem, you should read the class #05 exercise sheet]

In this problem you should submit a function as described. Inside the function do not print anything that was not asked!

[IP047] Which one?

A soft yet commanding voice echoed from behind you: "Aha! I see you’ve been quite busy with the whimsical challenges of Wonderland," Alice said, brushing a strand of hair behind her ear. "But I have an ultimate challenge for you — a real test of your skills!"

Alice took a step closer and continued, "You see, after observing all the transformations of words and how they evolve, I want to know a specific detail about these words. I want to find the n-th letter of the final transformed word in the White Rabbit’s word evolution game. But I need this to be speedier than a Cheshire Cat disappearing in a puff of smoke!"

The Problem

Write a function whichone(n) that given an integer n, returns the n-th letter (the one in position n) that appears on a word evolving from Mad Hatter's word game when starting with initial="A". Recall the rules of the game:

• Any 'A' becomes 'AB'
• Any 'B' becomes 'A'

The first lines of the word are therefore:

A
AB
ABA
ABAAB
ABAABABA
ABAABABAABAAB
ABAABABAABAABABAABABA

You can see that the initial part of any generation is the same as the previous, so you really don't need to know the generation and knowing the position is enough, right?

Constraints

The following limits are guaranteed in all the test cases that will be given to your program:

NOTE: the limits are really high and you must have an efficient solution that can compute this very quickly.
A solution that simply tries to simulate the evolution and recreate the entire word up to n will most likely have Time Limit Exceeded.
Your program will need to be able to answer around five hundred queries in less than one second.

print(whichone(1))
print(whichone(2))
print(whichone(3))
print(whichone(4))
print(whichone(5))
print(whichone(10))
print(whichone(16))

A
B
A
A
B
B
A