题目内容

小刚非常喜欢做数学题，这天小刚在做题的过程中看到了熟悉的斐波那契数列，已知斐波那契数列的通项公式为$F_{N+2}$ = $F_{n+1}$ + $F_n$ 。

同桌的小红趁小刚不注意的时候，偷偷的改了一下小刚试卷的题目，在数列的通项公式等式右边加上了两个常数 $A$ 和 $B$ 。已知数列 { $F_n$ }，其中$F_0$ 和 $F_1$ 均为 $1$ ，对于每一项 , $F_{n+2}$ = $F_{n+1}$ * $A$ + $F_n$ * $B$ 。

由于数列可能会很大，小刚只需要给出对应项（数列中的每一项）模上 $M$ 之后得出结果就行了。

输入描述

输入第一行为三个整数 $A$,$B$,$M$。 ($1$ <= $A$,$B$,$M$ <= $10^{8}$)

输入第二行为一个整数 $Q$ ,表示询问次数。($1$ <= $Q$ <= $50000$)

第三行输入$Q$个整数$q_i$表示查询数列的第$q_i$项模上数字M后的结果。($1$ <= $q_i$ <= $50000$)

输出描述

一行 $Q$ 个数，依次表示模上数字 $M$ 后的答案。

样例输入

输入

8 6 5
5
8 1 9 4 9

样例输出

输出

1 1 2 3 2