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
Sandeep Singh Jakhar: 2014-05-13 18:20:42

nice problem of karatsuba..!!

Vyron Drosos: 2014-05-13 18:20:42

to Ahmed Malatawy : runtime error means something like stack overflow happened, maybe you use too much memory.All the input cases will be as described in Input,no need to handle anything else

Ahmed Malatawy: 2014-05-13 18:20:42

Am i supposed to handle wrong input cases ? or even cases of inputting any type other than double ? I get a runtime error everytime

:D: 2014-05-13 18:20:42

Is that a criticism there XilinX? Because I, for one, LOVE constant optimization.

[Trichromatic] XilinX: 2014-05-13 18:20:42

@Ilyack: (1) You may try problem VFMUL. (2) Don't you think constant optimization is a tradition of SPOJ?

Ilya Porulyov: 2014-05-13 18:20:42

10000 (digits) is too less to measure is it really fast.
Well-coded \theta(n^2) algorithm is accepted. And technically non-efficiently coded but correct in asymptotics O(n^{\log_2{3}}) Karatsuba is non-accepted due to time overflow.

johnLate: 2014-05-13 18:20:42

If you have trouble with MUL, try TMUL first.

numerix: 2014-05-13 18:20:42

@jeshar: What do you think is the reason that there is no AC Python solution among the 1721 AC submissions so far?

rajesh: 2014-05-13 18:20:42

i am always getting nzec when i upload in python.can anyone tell me about this?

aparna: 2014-05-13 18:20:42

Even though I used BufferedReader I ended up getting TLE

Last edit: 2011-05-26 09:57: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