题目描述
Alice 正在思考一个关于 k 进制整数的问题。
普通的 k 进制可以将整数 n 表示为 dm−1dm−2⋯d0,且满足:
- 0≤di<k;
- n=i=0∑m−1diki。
然而,普通的 k 进制整数对于 Alice 来说太简单了,Alice 更喜欢奇怪的 k 进制整数。它与普通 k 进制整数的差别仅仅在于将 0≤di<k 换成了 di∈a,其中 a 为一个长为 D 的数列。
现在有一组固定的 a1,a2,⋯,aD,Alice 想要将 q 个十进制整数 n1,n2,⋯,nq 全部转化为奇怪的 k 进制整数,这种问题显然更适合写程序来解决。
输入格式
第一行,四个整数 k,q,D,M;
第二行,D 个整数 a1,a2,⋯,aD;
接下来 q 行,每行一个整数 ni。
输出格式
q 行,第 i 行表示 ni 转化后的结果,按幂次从高到低的顺序输出每一位,两个位之间用单个空格间隔。当 ai 中包含 0 时,你转化的结果可以包含前导零,但最好不要太多;当 ni=0 时,你转化的结果也不能为空。如果有多种方案可以随便输出一种,如果无法转化输出 IMPOSSIBLE
。
提示
本题由
https://www.luogu.com.cn/user/201007
。
数据范围
对于 100% 的数据,2≤k≤106,1≤q≤5,1≤D≤801,1≤M≤400,−M≤ai≤M,−1018≤ni≤1018。
题目来源
CCO2021 D1T2