Works
Petya is participating in a contest for young puzzle enthusiasts. In the final round, participants face the following challenge:
You are given an n×n square table. Next to each column and each row, a positive integer is written. The number next to the i-th column is x[i], and the number next to the j-th row is y[j]. To win the contest, you must place positive integers in some cells of the table such that the following conditions are satisfied:
All placed numbers must be distinct.
Each column and each row must contain exactly 2 numbers.
The product of the numbers in the
i-th column must equal x[i].The product of the numbers in the
j-th row must equal y[j].
The illustration shows an example solution to this problem.
Help Petya solve the puzzle!
Input
The first line contains the integer n (2 ≤ n ≤ 10). The second line contains n integers - x[1] ... x[n] (1 ≤ x[i] ≤ 1000 for all 1 ≤ i ≤ n). The third line also contains n integers - y[1] ... y[n] (1 ≤ y[i] ≤ 1000 for all 1 ≤ i ≤ n).
Output
Output the table after placing the numbers as required. The table should be output row by row: first the n numbers of the first row, then the n numbers of the second row, and so on. If a number is placed in a cell, output that number; if the cell remains empty, output 0. Separate all numbers with spaces and/or newlines. There is no need to worry about the neat formatting of the table. If there are multiple solutions, you may output any of them. It is guaranteed that at least one solution exists.