Fibonacci 词序列定义如下：$fib_0 = b, fib_1 = a, fib_n = fib_{n-1}fib_{n-2}$，其中 $n \ge 2$。$fib_n$ 是 $fib_{n-1}$ 和 $fib_{n-2}$ 的拼接。

前几个 Fibonacci 词为：$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$。

数据范围

• $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$

输出格式

对于每个测试用例，输出 $q$ 个值 $(sa_{p_1} \bmod m), (sa_{p_2} \bmod m), \dots, (sa_{p_q} \bmod m)$，用空格分隔。

样例

输入 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