Brandon likes Fibonacci numbers. For the purposes of this problem, the Fibonacci sequence is defined as the sequence of integers , where
, and
for
.
One day, Brandon writes down the sequence starting with
, except that because he does not have good arbitrary-precision arithmetics available to him, he
ends up writing down the values of
modulo
. He wants to know the
th digit he writes down for several different values of
.
Constraints
Input Specification
The first line contains two positive integers, and
.
The next lines each contain a single positive integer,
.
Output Specification
Output lines. On the
th line, output the
th digit that Brandon wrote down.
Sample Input 1
10 11
1
2
3
4
5
6
7
8
9
10
11
Sample Output 1
1
1
2
3
5
8
3
1
4
5
9
Sample Input 2
100 11
1
2
3
4
5
6
7
8
9
10
11
Sample Output 2
1
1
2
3
5
8
1
3
2
1
3
Comments