시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 512 MB | 1 | 1 | 1 | 100.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 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