M has a fraction $\frac a b$ that $a < b$, M is alone so he needs a sequence of fractions of length $l$ that satisfy following conditions:

• For each fraction $\frac p q$ in the sequence, $p$ must be less than $q$ ($p < q$).
• The multiplication of fractions must be equal to $\frac a b$ ($\prod_{i=1}^{l} \frac {p_i} {q_i} = \frac a b$).
• $1 \leq p, q \leq 10^{18}$

Input

The only input line contains three integers $a, b, l$ separated by space.

$1 \leq a, b \leq 10^8$

$1 \leq l \leq 10^3$

Output

The ouput should contains $l$ lines that each line contains $p_i, q_i$ separated by space, the fraction sequence which satisfy conditions, it there are multiple sequences print any of them.