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.