Reconstructing the Card Sequence

Alice never forgot the time when she existed in the world of cards. Magic brought a set of cards into her hand as well as Tanniel's, with each card inscribed with a positive integer, even though they now dwell in the realm of the Glass Kingdom.

Soon, the cards vanished and they set off on their journey. Alice only remembered the sum of the greatest common divisors (GCD) of every two adjacent cards, while Tanniel remembered the sum of the least common multiples (LCM) of every two adjacent cards.

Your task is to reconstruct a possible sequence of cards based on the remembered sums.

Formal Problem Statement

You are given q queries. Each query is in one of the following two forms:

• 1 n x: Find a sequence of n positive integers \(a_1, a_2, \ldots, a_n\) such that \(\sum_{i=1}^{n-1} \gcd(a_i,a_{i+1}) = x\).
• 2 n x: Find a sequence of n positive integers \(a_1, a_2, \ldots, a_n\) such that \(\sum_{i=1}^{n-1} \operatorname{lcm}(a_i,a_{i+1}) = x\).

Here, \(\gcd(\cdot,\cdot)\) and \(\operatorname{lcm}(\cdot,\cdot)\) denote the greatest common divisor and the least common multiple, respectively. If there are multiple solutions, any one is acceptable. If no solution exists, output -1.

Note: Every output integer must be a positive integer and fit within the C++ int type range.

inputFormat

The first line contains an integer q (the number of queries). Each of the next q lines contains a query in one of the two forms described:

• 1 n x
• 2 n x

It is guaranteed that n will be at least 2. For a valid solution, note that the minimal possible sum for adjacent pairs in both cases is when all numbers are 1, yielding n-1 (for GCD or LCM) as the sum. Thus, a necessary condition is that x ≥ n-1.

outputFormat

For each query, if a valid sequence exists, output a sequence of n positive integers separated by spaces on a single line such that the adjacent pairs satisfy the required sum. If no valid sequence exists, output -1 instead.

sample

3
1 4 5
1 3 3
2 4 5

3 3 1 1
2 2 1
3 1 1 1