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