BASECVT - Base Conversion (Easy)

We want to make some base-conversion experiments. Here you can try basic methods.

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 = a0×B10 + ... + ai×B1i + ... + ak-1×B1k-1

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            <--- Don't forget the length of N in base B2 ;-)
45 23 1

Explanations

For the lonely case, N = 5×100 + 4×101 + 3×102 + 2×103 + 1×104 = 12345.
We have: N = 45×1000 + 23×1001 + 1×1002. You have to print 3, the number of digits, then the digits: 45, 23 and 1.

Constraints

0 < T <= 200
1 < B1,B2 <= 10^9
1 < k <= 1000
0 <= ai < B1  , ak-1>0

If you find the constraints too easy, then you should try BASECONV.
The basic solution should give AC in 1.56s with Python3. (Edit 2017-02-11 : 0.42s with new compiler)
Have fun ;-)


Added by:Francky
Date:2014-03-19
Time limit:60s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own Problem

hide comments
2015-06-27 00:51:27 :.Mohib.:
In explaination:
N should be N = 45×100^0+ 23×100^1+ 1×100^2

=(Francky)=> Fixed ; thanks.

Last edit: 2015-06-27 10:32:20
2014-03-19 21:16:02 Mitch Schwartz
It seems my basic solution is more basic than your basic solution. :p
--ans(Francky)--> No, mine is simpler. But funny you're right. Simple = (B1 -> binary -> B2). Good luck ;-)
Edit : Don't forget to print the length in first line.
And I'll increase the time limit.

(Mitch) Thanks, you're right, that is a bit simpler. :)

Last edit: 2014-03-19 21:55:48
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.