Dytechlab Cup 2022 |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

constructive algorithms

math

number theory

*3300

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Ela and Prime GCD

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputAfter a long, tough, but fruitful day at DTL, Ela goes home happily. She entertains herself by solving Competitive Programming problems. She prefers short statements, because she already read too many long papers and documentation at work. The problem of the day reads: |

You are given an integer $$$c$$$. Suppose that $$$c$$$ has $$$n$$$ divisors. You have to find a sequence with $$$n - 1$$$ integers $$$[a_1, a_2, ... a_{n - 1}]$$$, which satisfies the following conditions:

- Each element is strictly greater than $$$1$$$.
- Each element is a divisor of $$$c$$$.
- All elements are distinct.
- For all $$$1 \le i < n - 1$$$, $$$\gcd(a_i, a_{i + 1})$$$ is a prime number.

In this problem, because $$$c$$$ can be too big, the result of prime factorization of $$$c$$$ is given instead. Note that $$$\gcd(x, y)$$$ denotes the greatest common divisor (GCD) of integers $$$x$$$ and $$$y$$$ and a prime number is a positive integer which has exactly $$$2$$$ divisors.

Input

The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) - the number of test cases.

The first line of each test case contains one integer $$$m$$$ ($$$1 \le m \le 16$$$) - the number of prime factor of $$$c$$$.

The second line of each test case contains $$$m$$$ integers $$$b_1, b_2, \ldots, b_m$$$ ($$$1 \le b_i < 2^{20}$$$) — exponents of corresponding prime factors of $$$c$$$, so that $$$c = p_1^{b_1} \cdot p_2^{b_2} \cdot \ldots \cdot p_m^{b_m}$$$ and $$$n = (b_1 + 1)(b_2 + 1) \ldots (b_m + 1)$$$ hold. $$$p_i$$$ is the $$$i$$$-th smallest prime number.

It is guaranteed that the sum of $$$n \cdot m$$$ over all test cases does not exceed $$$2^{20}$$$.

Output

Print the answer for each test case, one per line. If there is no sequence for the given $$$c$$$, print $$$-1$$$.

Otherwise, print $$$n - 1$$$ lines. In $$$i$$$-th line, print $$$m$$$ space-separated integers. The $$$j$$$-th integer of $$$i$$$-th line is equal to the exponent of $$$j$$$-th prime number from $$$a_i$$$.

If there are multiple answers, print any of them.

Example

Input

521 11131 1 11422 1

Output

0 1 1 1 1 0 1 0 1 1 0 0 1 1 0 1 1 1 0 0 1 0 1 1 1 1 0 0 -1 2 0 1 1 0 1 2 1 1 0

Note

In each test case, the values of $$$c$$$ are $$$6$$$, $$$2$$$, $$$30$$$, $$$16$$$, and $$$12$$$ in that order.

In the first test case, $$$1$$$, $$$2$$$, $$$3$$$, $$$6$$$ are divisors of $$$6$$$. Here, sequences $$$[2, 6, 3]$$$ and $$$[3, 6, 2]$$$ can be answer. Permutation $$$[3, 2, 6]$$$ is invalid because $$$\gcd(a_1, a_2) = 1$$$ is not a prime number.

In the forth test case, $$$1$$$, $$$2$$$, $$$4$$$, $$$8$$$, $$$16$$$ are divisors of $$$16$$$. Among the permutation of sequence $$$[2, 4, 8, 16]$$$, no valid answer exist.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/18/2024 13:55:34 (l2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|