BASECONV  Base Conversion
Leo didn't do all the job in his last problem, somebody gave him the numbers in a convenient base. It was the bottleneck of the problem... Now your task is to do this job.
Input
The first line of input contains three integers
T, the number of test cases,
B1, the first base,
B2, the second base.
Follow 2×T lines.
For each test case, on the first line your are given one integer k.
On the second line you are given k integers : the digits of N in base B1.
N = a_{0}×B1^{0} + ... + a_{i}×B1^{i} + ... + a_{k1}×B1^{k1}
Output
For each test case, you have to print the number N in base B2. See sample for details.
Example
Input: 1 10 100 5 5 4 3 2 1
Output: 3 45 23 1
Explanations
For the lonely case, N = 5×10^{0} + 4×10^{1} + 3×10^{2} + 2×10^{3} + 1×10^{4} = 12345.
We have: N = 45×100^{0} + 23×100^{1} + 1×100^{2}. You have to print 3, the number of digits,
then the digits: 45, 23 and 1.
Constraints
0 < T <= 50 1 < B1,B2 <= 10^9 1 < k <= 10000 0 <= a_{i} < B1 , a_{k1}>0
Time limit is sqrt(T_basic_pike_code * T_awaited_python_code) = sqrt(13.34*6.97), based on my Python3/Pike experiments.
You may try before the tutorial edition.
Have fun ;)
Time limit is sqrt(T_basic_pike_code * T_awaited_python_code) = sqrt(3.93*1.57), based on my Python3/Pike experiments.
Thanks @Blue_Mary for pointing this out.
hide comments
Min_25:
20170824 11:44:04
@liouzhou_101: I often see http://www.spoj.com/comments/all/ to remove/report some comments. 

liouzhou_101:
20170824 05:27:54
@Min_25 Thank you for sharing it. Moreover, I wonder how you can discover my comment so soon? 

Min_25:
20170824 01:02:00
@liouzhou_101: It needs some preparation (cf. https://ideone.com/NLKgGo). (I learned it from some contestants.) 

liouzhou_101:
20170823 18:24:16
@Min_25 How do you use GMP in your C++14 code? I found that simply include GMP can lead to CE. 

Robert Lewon:
20170426 11:17:09
We have announced compiler changes in our blog entry: http://blog.spoj.com/index.php/2017/02/10/thebigupdatemorelanguagesavailablethaneverbefore/. Some libraries (like GMP) could become a part of the standard set of libraries in updated versions.


Michael Kharitonov:
20170425 23:29:46
GMP is avalible?! Since compiler update in February or since even before that? And why cluster is still showing "Intel G860" when it is actually "Intel Xeon E31220 v5"? How big is memory limit?


Min_25:
20170425 22:01:11
My C++14 solution uses GMP. So, the complexity is O(M(k) log(k)).


Michael Kharitonov:
20170425 19:11:21
Got AC with complexity k^2 per test. Just curious what are the complexities for mentioned solutions in Pike and Python and have anyone wrote k*log^2(k) solution.


[Rampage] Blue.Mary:
20170211 17:34:02
The time limit of this problem should be updated: with updated pike compiler ver 8.0, pike code gets 45 times faster. Please do it ASAP.


Michael Kharitonov:
20170206 09:25:24
Nice problem, maybe you or me should set a hard one with expected complexity k*log^2(k) per test.

Added by:  Francky 
Date:  20140319 
Time limit:  2.483s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own Problem 