Fibonacci Suffix Array

The Fibonacci words are defined as follows: $fib\_0=b, fib\_1=a, fib\_n=fib\_{n-1}fib\_{n-2} \text{ for } n \ge 2$. $fib\_n$ is the concatenation of $fib\_{n-1}$ and $fib\_{n-2}$.

The first few Fibonacci words are $b$, $a$, $ab$, $aba$, $abaab$, $abaababa$, $abaababaabaab$, $\dots$

A suffix array for a string $s$ of length $n$ is a permutation $sa$ of the integers from $1$ to $n$ such that $s\[sa\_1.. n], s\[sa\_2..n], \dots, s\[sa\_n..n]$ is the list of all non-empty suffixes of $s$ in lexicographical order.

Let $sa$ be the suffix array of $fib\_n$. Compute $(sa\_{p\_1} \bmod m), (sa\_{p\_2} \bmod m), \dots, (sa\_{p\_q} \bmod m)$.

The input contains several test cases and ends at end-of-file. Each test case has the following format.

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

The second line contains $q$ integers $p\_1, p\_2, \dots, p\_q$.

For each test case, print $q$ values $(sa\_{p\_1} \bmod m), (sa\_{p\_2} \bmod m), \dots, (sa\_{p\_q} \bmod m)$ separated by spaces.

• $1 \le n \le 10^{18}$
• $1 \le q \le 10^5$
• $1 \le m \le 2 \times 10^9$
• $1 \le p\_i \le \min(10^{18}, |fib\_n|)$
• The sum of $q$ over all test cases does not exceed $10^6$.