시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 0 0 0 0.000%

문제

The sequence of Fibonacci words is 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 string $s$ of length $n$ is a permutation $sa$ of integers from $1$ to $n$ such that $s[sa_1.. n], s[sa_2..n], \dots, s[sa_n..n]$ is the list of non-empty suffixes of $s$ sorted in lexicographical order.

Let $sa$ be the suffix array for $fib_n$. Your task is to calculate the value of $(sa_{p_1} \bmod m), (sa_{p_2} \bmod m), \dots, (sa_{p_q} \bmod m)$.

입력

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 $p_1, p_2, \dots, p_q$.

출력

For each test case, output $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$ does not exceed $10^6$.

예제 입력 1

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
1 2
3 1 2
3 4 1 5 2
8 3 6 1 4 7 2 5