The sequence of Fibonacci words is defined as follows: . is the concatenation of and .

The first few Fibonacci words are: b, a, ab, aba, abaab, abaababa, abaababaabaab,

A suffix array for string s of length n is a permutation sa of integers from 1 to n such that is the list of non-empty suffixes of s sorted in lexicographical order.

Let sa be the suffix array for . You task is to calculate the value of .

The input consists of several test cases terminated by end-of-file. For each test case:

The first line contains three integers n, q and m.

The second line contains q integers .

* 
* 
* 
* 
* The sum of q does not exceed .

For each test case, output q values , separated by spaces.

1 1 10
1
2 2 10
1 2
3 3 10
1 2 3
4 5 10
1 2 3 4 5
5 8 10
1 2 3 4 5 6 7 8

1 
1 2 
3 1 2 
3 4 1 5 2 
8 3 6 1 4 7 2 5