Problem E
Products
Input: Standard Input

Output: Standard Output

Time Limit: 4 Seconds

 

Peter takes part in a computational mathematics contest. The last round consists of the following problem.

Given an array . A positive integer is written besides each column and row. Let be a number written near a column , and a number written near a column . In order to be a winner a few numbers should be put in the array. Moreover, it’s absolutely necessary to follow all the conditions described lower:

        1) No two numbers in the array may be equal.

        2) Each column and each row must contain exactly two numbers.

        3) The product of the numbers of - th column must be equal to Xi.

        4) The product of the numbers of - th row must be equal to .

 

Figure 1 shows the example of a solution of such a problem.

 

Figure - 1

 

Please! Help Peter.

 

Input

The input file contains several test cases. The description of each test case is given below:

 

The first line of each test case contains  N (2<=N<=10). The second line contains N numbers, X1, X2 … XN  (1<=Xi<=1000 for all 1<=i<=N). The third line contains N numbers Y1, Y2 … YN  (1<=Yi<=1000 for all 1<=i<=N).

 

Input is terminated by a case whose N=0. This case should not be processed.

 

Output

The description of output for each test case is given below:

 

For each set of input print the (N*N) grid after placing the numbers in it. The array should be printed by lines: first N numbers of the first row, then N numbers of the second row, etc. If the cell has a number - print it; however, if it does not - print just 0. All the numbers should be separated by blanks and/or new line symbols. It’s not necessary to care about nice array. If there are many solutions, find just one of it. It's guaranteed that at least one solution will always exist.

 

Print a blank line after the output for each set of input.

 

Sample Input                               Output for Sample Input

2

2 12

3 8

3

5 8 18

2 30 12

5

54 6 12 20 88

18 9 132 32 10

10

2 12 30 56 90 132 182 240 306 380

19 36 51 64 75 84 91 96 99 200

0

  1   3

  2   4

 

  1   2   0

  5   0   6

  0   4   3

 

  6   3   0   0   0

  9   0   1   0   0

  0   0  12   0  11

  0   0   0   4   8

  0   2   0   5   0

 

  1   0   0   0   0   0   0   0   0  19

  2   0   0   0   0   0   0   0  18   0

  0   3   0   0   0   0   0   0  17   0

  0   4   0   0   0   0   0  16   0   0

  0   0   5   0   0   0   0  15   0   0

  0   0   6   0   0   0  14   0   0   0

  0   0   0   7   0   0  13   0   0   0

  0   0   0   8   0  12   0   0   0   0

  0   0   0   0   9  11   0   0   0   0

  0   0   0   0  10   0   0   0   0  20

 

Problemsetter: Andrew Stankevich, From a Russian Local Contest.

Supplier & Translator: Dima Chernysh

Special Judge, Conversion to UVA format: Shahriar Manzoor