MUL2COM - Binary multiplication


In this problem, you have to multiply two n-bit binary numbers in 2s complement form. The result should be also a n-bit binary number in 2s complement form. In case there is an arithmetic overflow, you program should be able to detect it.

For your information, the 2s complement form of -x is the number 2^n-x. A n-bit 2s complement number ranges from -2n-1 to 2n-1-1.

Input

There are multiple test cases (no more than 40). For each test case, there are three input lines. The first line contains n (0 ≤ n ≤ 1024). n=0 signals the end of the input. Otherwise, the second and third lines contain the two n-bit binary numbers.

Output

For each test case, output "overflow" if there is an arithmetic overflow. Otherwise, print the result in 2s complement form.

Example

Input
3
110
011
4
0011
1110
0

Output
overflow
1010

hide comments
:.Mohib.:: 2015-07-11 13:42:06

@Duc can you please check my last submission I think it's correct but WA here :(

Vaibhav Agarwal: 2013-08-15 06:23:19

easy one.... AC in first attempt! :D
@rajeev the answer is: 10

Last edit: 2013-08-15 06:30:00
rajeev bhardwaj: 2013-06-20 06:33:14

what will be the output for :
2
10
01
???

rajeev bhardwaj: 2013-06-20 06:15:45

please show some other test cases ?

Last edit: 2013-06-20 06:30:08
daft_wullie: 2013-04-15 13:55:15

@Tushar Makkar: Because 1110 in 2s complement corresponds to -2 in decimal (not 14!!!)

Tushar Makkar (Retired): 2013-04-04 12:22:20

can anybody please explain me the 2nd test case ? Why is it not giving overflow although the answer is far beyond the range specified ?

:D: 2011-03-18 16:25:17

I don't understand the question. The input values are in 2s if you are asking that.

nagesh: 2011-03-18 14:49:47

do we have to take ....2s of both numbers while multiplying???

Jargon: 2010-05-13 22:21:40

This is how I remember twos complement form:
The 2s complement form of -x is (x - 1) in binary, inverted.
EG the 2s complement of -13 with 8 bits is the binary form of 12 (00001100) inverted (11110011).

Anil: 2009-12-21 19:28:37

the 2s complement form of -x is the number 2^n-x.
can any one explain with example what the above sentence means?. Thanks :)


Added by:Duc
Date:2008-09-10
Time limit:0.204s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP clisp LISP sbcl D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM guile SCM qobi ST WHITESPACE
Resource:© VNOI