Mr. Bean drinks from a water bottle that he carried for a long time without re lling, and
the stale water has resulted in him su ering from mild dysentery. He goes to a nearby nursing
home and gets diagnosed with Amoebiasis. The doctor identi es the pathogen to be a partic-ular kind of amoeba that has two variants, namely Asperdabrum (a) and Bostonostrum (b).
Each amoeba reproduces every hour by splitting into two, a !ab, and b !ba, and they stick
together in a chain in that particular sequence. At every step of reproduction, all the present
amoeba undergo binary ssion. For e.g. starting with type a, after 1st step the chain is ab,
after 2nd step the chain is abba, after the 3rd step the chain is abbabaab and so on. Mr.Bean
was infected n hours ago by a single amoeba and the doctor needs to know the type of the kth amoeba in the chain present now to be able zo nd a cure. Help the doctor cure him.
Input Format:
First line contains the number of test cases T. For each test case, there will be a single line of
input that starts with a character denoting the type of amoeba, , that infected him initially (a
or b) followed by two integers, n - the number of hours that have passed since he was infected,
and k - the position at which the doctor needs to know the type of amoeba.
Limits: 1<= T<=1000000, 1<= N<=4100, 1<=K<=2^N
.
Moreover, for the rst test le you can assume N, K lie within integer range (32 bits).
Output Format:
For each test case, output on a separate line the type of the kth amoeba in the current chain.
Sample Input:
2
a 3 3
b 4 6
Sample Output:
b
b
Source BITWise IITKGP,
the stale water has resulted in him su ering from mild dysentery. He goes to a nearby nursing
home and gets diagnosed with Amoebiasis. The doctor identi es the pathogen to be a partic-ular kind of amoeba that has two variants, namely Asperdabrum (a) and Bostonostrum (b).
Each amoeba reproduces every hour by splitting into two, a !ab, and b !ba, and they stick
together in a chain in that particular sequence. At every step of reproduction, all the present
amoeba undergo binary ssion. For e.g. starting with type a, after 1st step the chain is ab,
after 2nd step the chain is abba, after the 3rd step the chain is abbabaab and so on. Mr.Bean
was infected n hours ago by a single amoeba and the doctor needs to know the type of the kth amoeba in the chain present now to be able zo nd a cure. Help the doctor cure him.
Input Format:
First line contains the number of test cases T. For each test case, there will be a single line of
input that starts with a character denoting the type of amoeba, , that infected him initially (a
or b) followed by two integers, n - the number of hours that have passed since he was infected,
and k - the position at which the doctor needs to know the type of amoeba.
Limits: 1<= T<=1000000, 1<= N<=4100, 1<=K<=2^N
.
Moreover, for the rst test le you can assume N, K lie within integer range (32 bits).
Output Format:
For each test case, output on a separate line the type of the kth amoeba in the current chain.
Sample Input:
2
a 3 3
b 4 6
Sample Output:
b
b
Source BITWise IITKGP,
