解题思路

本题给出了一个递推序列的递推式：

• $x_0 = 1$，$x_1 = 1$
• $x_{i+2} = (c_1 \cdot x_{i+1} + c_2 \cdot x_i) \bmod p$

题目内容

有一个整数序列 $x_0, x_1, x_2, \dots$，其中 $x_0 = 1 \bmod M$, $x_1 = 1 \bmod M$，且对于所有 $i \ge 0$，满足 $x_{i+2} = (A \cdot x_{i+1} + B \cdot x_i) \bmod M$。

给定系数 $A, B$ 和模数 $M$，以及若干询问，请你对每个询问输出对应位置的序列值。

保证 $1 \le A, B, M \le 10^8$，询问次数 $q$ 满足 $1 \le q \le 50000$，每次询问的下标 $k$ 满足 $1 \le k \le 50000$。

输入描述

第一行包含三个整数 $A, B, M$。 第二行包含一个整数 $q$，表示询问次数。 第三行包含 $q$ 个整数 $k_1, k_2, \dots, k_q$，表示需要查询的下标。

输出描述

输出一行，包含 $q$ 个整数，用空格分隔，依次表示每个询问的答案。

样例1

输入

3 2 7
5
1 2 3 4 5

输出

1 5 3 5 0

说明

序列初始值为 $x_0 = 1, x_1 = 1$。给定 $c_1 = 3, c_2 = 2, p = 7$。 递推计算：

• $x_2 = (3 \times 1 + 2 \times 1) \bmod 7 = 5$
• $x_3 = (3 \times 5 + 2 \times 1) \bmod 7 = 17 \bmod 7 = 3$
• $x_4 = (3 \times 3 + 2 \times 5) \bmod 7 = 19 \bmod 7 = 5$
• $x_5 = (3 \times 5 + 2 \times 3) \bmod 7 = 21 \bmod 7 = 0$ 因此对于查询下标 1, 2, 3, 4, 5，依次输出 1, 5, 3, 5, 0。

样例2

输入

1 1 10
6
1 2 3 4 5 6

输出

1 2 3 5 8 3

说明

该组参数下递推式变为 $x_{i+2} = (x_{i+1} + x_i) \bmod 10$，即斐波那契数列模 $10$。 $x_0 = 1, x_1 = 1$；

• $x_2 = (1 + 1) \bmod 10 = 2$
• $x_3 = (2 + 1) \bmod 10 = 3$
• $x_4 = (3 + 2) \bmod 10 = 5$
• $x_5 = (5 + 3) \bmod 10 = 8$
• $x_6 = (8 + 5) \bmod 10 = 3$ 查询下标 1 到 6 对应上述值，输出 1 2 3 5 8 3。

样例3

输入

1 1 10
3
10 20 50000

输出

9 6 6

说明

同样是 $x_{i+2} = (x_{i+1} + x_i) \bmod 10$。前几项为 $1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9$（$x_0$ 到 $x_{10}$），因此 $x_{10} = 9$。 继续递推可得 $x_{20} = 6$。模 $10$ 下该序列的周期为 $60$，而 $50000 \equiv 20 \pmod{60}$，故 $x_{50000} = x_{20} = 6$。 即使 $k$ 达到 $50000$，也能通过递推或周期性得到结果。输出 9 6 6。