时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
题目描述
初始给定三个整数
，分别代表底数，幂数，模数。
对于任意的
，都有
%20%5C%25%20mod)
。
给定
次询问，每次询问给出一个整数
，请你求出
%20%5C%25%20mod)
的值。
特别地，我们定义
。
输入描述:
第一行有三个整数 %5C%20%2C%5C%20(%5C%201%20%5Cleq%20mod%20%5Cleq%2010%5E6%5C%20))
。
第二行有一个整数 )
。
随后 
行，每行一个整数 )
。
输出描述:
输出 行，每行一个整数，代表 %20%5C%25%20mod)
的值。
示例2
输入
复制
1919 810 114514
5
76
114514
1919810
1000000000
1000000000000000000
输出
复制
3624
80720
63830
32422
97088