GLCCDM

Time limit1sMemory limit1024 MB

Summary

Given A, B, and K, the task asks for K distinct positive integers with gcd equal to A and lcm equal to B, or -1 if none exist.

Level: Medium6 of 10
Topics: Number theory, Math, Combinatorics
Solved: No attempts yet

Problem

Find a sequence $d_1, \cdots, d_K$ of $K$ distinct positive integers that satisfies both $\operatorname{gcd}(d_1, \cdots, d_K) = A$ and $\operatorname{lcm}(d_1, \cdots, d_K) = B$ .

Input

The first line contains positive integers $A$ , $B$ , and $K$ separated by spaces. ( $1 \le A < B \le 1\,000\,000$ ; $2 \le K \le 100$ )

Output

Print $K$ positive integers $d_1, \cdots, d_K$ separated by spaces, in any order. If several sequences satisfy the conditions, print any one of them. If no sequence satisfies the conditions, print only -1.

Hint

$\gcd(d_1, \cdots, d_K)$ is the largest positive integer that divides every $d_i$ , and $\operatorname{lcm}(d_1, \cdots, d_K)$ is the smallest positive integer that every $d_i$ divides.

Examples2

Example 1
Input
```
2 36 3
```
Expected output
```
4 6 18
```
Example 2
Input
```
2 8 5
```
Expected output
```
-1
```