Problem Description

Alice has never forgotten that she once existed in the world of playing cards.

So magic made some cards appear in her hand. Magic also made some cards appear in Taniel’s hand, and on each card there was a positive integer—even though they are now in the Glass Kingdom.

The cards quickly vanished, and they were ready to set off. Alice only remembered the sum of the greatest common divisors of each pair of adjacent cards, and Taniel only remembered the sum of the least common multiples of each pair of adjacent cards.

You are still in this palace, and you want to recreate the cards from that time.

Formal statement

You are given $q$ queries. Each query is one of the following two types:

• 1 n x means you need to output a positive integer sequence $\{a_n\}$ of length $n$, such that $\sum\limits_{i=1}^{n-1} \gcd(a_i,a_{i+1})=x$.

• 2 n x means you need to output a positive integer sequence $\{a_n\}$ of length $n$, such that $\sum\limits_{i=1}^{n-1} \operatorname{lcm}(a_i,a_{i+1})=x$.

Also, for any output, each $a_i$ must not exceed the storage range of int in C++.

Here, $\gcd$ and $\operatorname{lcm}$ are the greatest common divisor and least common multiple. If there are multiple solutions, you may output any one. If there is no solution, output -1.

Input Format

The first line contains a positive integer $q$, the number of queries.

Then follow $q$ lines. Each line contains three positive integers $op,n,x$.

• When $op=1$, it means Alice has $n$ cards and the sum she remembered is $x$. You need to restore her cards.

• When $op=2$, it means Taniel has $n$ cards and the sum he remembered is $x$. You need to restore his cards.

Output Format

Output $q$ lines. On each line, output an integer sequence for the card sequence you construct for that query. Adjacent numbers in the sequence should be separated by a single space.

If there are multiple solutions, you may output any one. If there is no solution, output -1.

5
1 5 4
2 3 8
1 5 10
2 6 34
1 3 1

1 1 1 1 1
2 2 3
1 1 1 7 7
1 1 4 5 1 4
-1

Hint

Constraints

This problem uses bundled testdata.

Special property $\text{A}$: it is guaranteed that for every query, $op=1$.

Special property $\text{B}$: it is guaranteed that for every query, $op=2$.

For $100\%$ of the data, $2\le n\le 5\times 10^5$, $2\le \sum n\le 5\times 10^5$, $1\le x \le 2^{31}-1$, and $op\in\{1,2\}$.

Translated by ChatGPT 5