Indian National Olympiad in Informatics

Related:

Online Programming Contest, 5-6 March 2005

IARCS home > OLYMPIAD

Basic Division

Problem 1: Base b Arithmetic, (K Narayan Kumar, CMI)

Traditionally numbers are written in base 10 ("decimal"). That is, every digit is a number between 0 and 9. We think of a number as its decimal representation. However, as you might know, numbers can be written in base b for any b > 0. In this case, every digit is a number between 0 and b-1. For instance in base 4 we may write 3312 or 30.

The value of a number written in base b is determined as follows: Suppose the given number in base b is d_n-1 ... d₀ where each d_i lies between 0 and b-1. This represents the number

d₀ + d₁ * b + d₂ * b² + ... + d_i * bⁱ + ... + d_n-1 * b^n-1

We don't permit leading 0's in the representation. For instance, we cannot write 003312 or 03312 instead of 3312.

Given a number in decimal one can compute the base b representation by inverting the above computation.

It is easy to check that the base 4 representation 3312 denotes the decimal number 246 and the base 4 representation 30 denotes 12. Similarly, the base 12 representation 2 11 10 (where we use blank spaces to separate the digits) denotes the decimal number 430 while the base 12 representation 3 0 2 denotes the number 434.

You will be given b and the base b representation of two numbers A and B. Your task is to printout the base b representation of the product A ×B.

For example the product of the base 4 numbers 3312 and 30 written in base 4 is 232020. Similarly, the product of the base 12 numbers 2 11 10 and 3 0 2 written in base 12 is 8 11 11 11 8.

Input format

The first line of the input contains 3 integers b, N and M, where b is the base. N and M are the number of digits in the representation (in base b) of the two given numbers.

The second line contains N space separated integers D_N-1 D_N-2 ... D₀ giving the base b representation of the first number and the third line contains M space separated integers E_M-1 E_M-2 ... E₀ giving the base b representation of the second number.

Output format

The first line of the output should be a single integer L denoting the length of the base b representation of the product. The second line should contain L space separated integers giving the base b representation of the product.

Test data

You may assume that 1 ≤ N,M ≤ 1000.

Example

We now illustrate input and output formats using the examples described above.

Sample input 1:

4 4 2
3 3 1 2
3 0

Sample output 1:

6
2 3 2 0 2 0

Sample input 2:

12 3 3 
2 11 10
3 0 2

Sample output 2:

5
8 11 11 11 8