409569: GYM103633 C Yet Another Constructive Problem

This problem has $$$t$$$ ($$$1 \le t \le 10^5$$$) testcases.

In each testcase you are given two integers $$$N$$$ and $$$M$$$ ($$$1 \le N,M \le 2 \cdot 10^3$$$), and two arrays $$$a=[a_1,a_2,\ldots,a_n]$$$ and $$$b=[b_1,b_2,\ldots,b_m]$$$.

For each testcase, you will have to find any matrix of positive integers $$$ans$$$ with $$$N$$$ rows and $$$M$$$ coloumns which satisfies the following constraints:

1. For any row $$$i \in [1,N]$$$, the product of the elements in that row is equal to $$$a_i$$$. More formally, $$$(\forall i \in [1,N])(\prod_{j=1}^M ans_{i,j}=a_i)$$$.
2. For any coloumn $$$j \in [1,M]$$$, the product of the elements in that coloumn is equal to $$$b_j$$$. More formally, $$$(\forall j \in [1,M])(\prod_{i=1}^N ans_{i,j}=b_j)$$$.

If there are no matrices satisfying the given constraints, simply print "-1", without the quotes. Otherwise, if there are multiple matrices satisfying the given constraints, you may print any of them.

The first line of input contains one integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of testcases. The following $$$3\cdot t$$$ lines of input contain the descriptions of the testcases, $$$3$$$ lines per testcase:

The first line of each testcase contains two integers $$$N$$$ and $$$M$$$ ($$$2 \le N,M \le 2 \cdot 10^3$$$).

The second line of each testcase contains $$$N$$$ integers $$$a_1,a_2, \ldots a_n$$$ ($$$1 \le a_i \le 10^9, \forall i \in [1,n]$$$) — the elements of array $$$a$$$.

The third line of each testcase contains $$$M$$$ integers $$$b_1,b_2, \ldots b_m$$$ ($$$1 \le b_i \le 10^9, \forall i \in [1,m]$$$) — the elements of array $$$b$$$.

It is guaranteed that, across all testcases, the sum of $$$N \cdot M$$$ does not exceed $$$5 \cdot 10^6$$$. More formally, it is guaranteed that $$$\sum N \cdot M \le 5 \cdot 10^6$$$.

For each testcase, if there exists some matrix $$$ans$$$ satisfying the given constraints, print $$$N$$$ lines containing the elements of matrix $$$ans$$$, $$$M$$$ integers per line. Otherwise, simply print "-1", without the quotes.

If there are multiple matrices satisfying the given constraints, you may print any of them.

3
4 5
20 12 27 15
6 30 45 4 3
3 3
1 1 1
2 1 1
6 5
2808 1 180 1980 1001 945
16632 630 1 23166 3900

2 10 1 1 1
3 1 1 4 1
1 3 9 1 1
1 1 5 1 3

-1

24 9 1 1 13
1 1 1 1 1
9 10 1 2 1
11 1 1 9 20
1 7 1 143 1
7 1 1 9 15

Note that the sample output has extra line breaks for added clarity between consecutive testcases.