피보나치 접미사 배열

피보나치 단어는 다음과 같이 정의한다. $fib\_0=b, fib\_1=a, fib\_n=fib\_{n-1}fib\_{n-2} \text{ for } n \ge 2$. $fib\_n$은 $fib\_{n-1}$과 $fib\_{n-2}$를 이어 붙인 문자열이다.

처음 몇 개의 피보나치 단어는 $b$, $a$, $ab$, $aba$, $abaab$, $abaababa$, $abaababaabaab$, $\dots$이다.

길이가 $n$인 문자열 $s$의 접미사 배열은 1부터 $n$까지의 정수를 원소로 하는 순열 $sa$이며, $s\[sa\_1.. n], s\[sa\_2..n], \dots, s\[sa\_n..n]$이 $s$의 비어 있지 않은 모든 접미사를 사전순으로 나열한 목록이 되도록 한다.

$sa$를 $fib\_n$의 접미사 배열이라고 하자. $(sa\_{p\_1} \bmod m), (sa\_{p\_2} \bmod m), \dots, (sa\_{p\_q} \bmod m)$의 값을 구하라.

입력은 여러 테스트 케이스로 이루어지며, 파일의 끝(EOF)에서 끝난다. 각 테스트 케이스는 다음 형식이다.

첫 줄에 정수 $n$, $q$, $m$이 주어진다.

둘째 줄에 $q$개의 정수 $p\_1, p\_2, \dots, p\_q$가 주어진다.

각 테스트 케이스마다 $(sa\_{p\_1} \bmod m), (sa\_{p\_2} \bmod m), \dots, (sa\_{p\_q} \bmod m)$의 $q$개 값을 공백으로 구분하여 출력한다.

• $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|)$
• 모든 테스트 케이스의 $q$ 합은 $10^6$을 넘지 않는다.