Hide

Problem A
Batmanacci

The Fibonacci sequence can be defined as follows:

fib1=1fib2=1fibn=fibn2+fibn1

We get the sequence 1,1,2,3,5,8,13,21,. But there are many generalizations of the Fibonacci sequence. One of them is to start with other numbers, like:

f1=5f2=4fn=fn2+fn1

And we get the sequence 5,4,9,13,22,35,57,. But what if we start with something other than numbers? Let us define the Batmanacci sequence in the following manner:

s1=Ns2=Asn=sn2+sn1

where + is string concatenation. Now we get the sequence N, A, NA, ANA, NAANA, ….

Given N and K, what is the K-th letter in the N-th string in the Batmanacci sequence?

Input

Input consists of a single line containing two integers N (1N105) and K (1K1018). It is guaranteed that K is at most the length of the N-th string in the Batmanacci sequence.

Output

Output the K-th letter in the N-th string in the Batmanacci sequence.

Sample Input 1 Sample Output 1
7 7
N
Sample Input 2 Sample Output 2
777 777
A
Hide

Please log in to submit a solution to this problem

Log in