Brandon likes Fibonacci numbers. For the purposes of this problem, the Fibonacci sequence is defined as the sequence of integers ~f~, where ~f_1 = f_2 = 1~, and ~f_i = f_{i-1} + f_{i-2}~ for ~i \ge 3~.

One day, Brandon writes down the sequence ~f~ starting with ~f_1~, except that because he does not have good arbitrary-precision arithmetics available to him, he ends up writing down the values of ~f_i~ modulo ~M~. He wants to know the ~N~th digit he writes down for several different values of ~N~.

Constraints

~2 \le M \le 10^4~

~1 \le N_i \le 10^{18}~

~1 \le Q \le 10^6~

Input Specification

The first line contains two positive integers, ~M~ and ~Q~.

The next ~Q~ lines each contain a single positive integer, ~N_i~.

Output Specification

Output ~Q~ lines. On the ~i~th line, output the ~N_i~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