MUL - Fast Multiplication


Multiply the given numbers.

Input

n [the number of multiplications <= 1000]

l1 l2 [numbers to multiply (at most 10000 decimal digits each)]

Text grouped in [ ] does not appear in the input file.

Output

The results of multiplications.

Example

Input:
5
4 2
123 43
324 342
0 12
9999 12345

Output:
8
5289
110808
0
123437655

Warning: large Input/Output data, be careful with certain languages


hide comments
algo_aris: 2015-12-08 17:03:38

Interesting task, because even in Java implementation of BigInteger in 6 lines works faster than Karatsuba

darkhire21: 2015-11-04 13:03:24

if you want to learn something new do it in c++/c.

abdiazizelmi_1: 2015-10-12 21:17:47

Using C# in visual studio 2015, it executes fine but here it says compilation error. Please spoj upgrade your compilers.

Last edit: 2015-10-12 21:23:57
guneet_1995: 2015-08-25 19:17:17

AC ;) learnt about java.math.BigInteger class and using its variables.

skrishna99: 2015-08-16 11:02:59

In my Pc I get correct answer for all sample input , Ideone it compiled successfully . But I get WA in SPOJ please help.

ranvirsingh: 2015-08-12 05:48:34

0 line code in c. Don't do it.

Last edit: 2015-08-12 05:48:50
prakash_reddy: 2015-08-11 19:12:44

Easy in java.... :)

ranjeetkumar: 2015-08-09 08:50:46

5 line code in java.......easy one(use biginteger)
nextline cause one wrong answer....

guneet_1995: 2015-08-05 21:41:01

I submitted it 4 times my id no. is 14829752
runs properly but judge saying wrong Answer please help!

Hikari9: 2015-07-26 07:24:04

Use fast fourier transform for GCC. Either that, or group digits into groups of 10


Added by:Darek Dereniowski
Date:2004-06-01
Time limit:1.649s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:PAL