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*_{0} where each
*d*_{i} lies between 0 and *b*-1. This
represents the number

*d*_{0} + *d*_{1} * *b* +
*d*_{2} * *b*^{2} + ... +
*d*_{i} * *b*^{i} + ... +
*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*_{0} 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*_{0} 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

Copyright (c) IARCS 2003-2018; Last Updated: 29 Mar 2005