VFMUL - Very Fast Multiplication

Multiply the given numbers.

Input

n [the number of multiplications <= 101]

l1 l2 [numbers to multiply (at most 300000 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


Added by:Darek Dereniowski
Date:2004-11-27
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6
Resource:PAL

hide comments
2014-05-24 14:05:34 Naman Goyal
Karatsuba with base 10^8 is getting TLE (which was getting AC for MUL). Can anyone give any leads as which FFT algorithm I should try to implement?
2014-05-13 18:20:59 Roman Sol
Is it possible to solve it with Schönhage–Strassen? It requires binary representation of digits not decimal.
2014-05-13 18:20:59 Emir Habul
Try problems MUL and TMUL first.

They are easier version of this.
2014-05-13 18:20:59 [Rampage] Blue.Mary
NTT can get Accepted too.
2014-05-13 18:20:59 Brian Bi
Longer numbers don't demand higher precision?
2014-05-13 18:20:59 [Trichromatic] XilinX
FFT (using double) CAN get Accepted.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.