## Another Contest 8 Problem 3 - Replay Double Ignition

View as PDF

Points: 10
Time limit: 0.25s
Memory limit: 1G

Problem type

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 .

#### 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