In what concerns the continuous evaluation solving exercises grade during the semester, you should submit until 23:59 of April 7th
(this exercise will still be available for submission after that deadline, but without couting 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 file containing the function as described (without any main function). Inside the function do not print anything that was not asked!

[PII040] Dracarys!

In the blazing heat of Dragonstone, Daenerys Targaryen, the Mother of Dragons, prepares for the wars to come. She is aware of how the Free Folks words evolve (from [PII039], the last problem), and has tasked you with a perilous challenge.

"When words grow like fire, finding one letter may change everything. I need you to tell me the k-th letter after these words evolve — quickly! Fail me, and you will face the wrath of my dragons!"

Can can solve this puzzle efficiently? Failure to do so will result in her commanding Drogon, Rhaegal and Viserion to unleash Dracarys, engulfing you on dragon fire.

The Problem

Write a function char which_one(long n) that, given an integer n, returns the n-th letter (the one in position n) that appears on a word evolving with the Free Folk rules when starting with "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:

Submission

You should submit a .c file containing the requested function, without any main function and without printing anything. You can however create additional methods, if you need them.

Mooshak will use the following code to link to your function, read the inputs and call your method, printing its result.

#include <stdio.h>
#include <string.h>

char which_one(long);

int main(void) {

  // Read amount of test cases
  int k;
  scanf("%d", &k);

  // Read n cases and for each call the which_one function
  for (int i=0; i<k; i++) {
    long n;
    scanf("%ld", &n);
    printf("which_one(%ld) = %c\n", n, which_one(n));
  }
  
  return 0; 
}

NOTE: the limits are really high and you must have an efficient (in space and memory) solution that can compute this very quickly.
The entire word will not fit on the memory of a personal computer and even if it did, a solution that simply tries to simulate the evolution and recreate the entire word up to n would most likely have Time Limit Exceeded.
Your program will need to be able to answer around 500 queries in less than one second.

7
1
2
3
4
5
10
16

which_one(1) = A
which_one(2) = B
which_one(3) = A
which_one(4) = A
which_one(5) = B
which_one(10) = B
which_one(16) = A